2598. Smallest Missing Non-negative Integer After Operations
Approach
Map each element to remainder mod value; find smallest integer with no fully-filled bucket.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Hash tables provide O(1) average-case lookup, insert, and delete. They are the go-to tool for counting frequencies, detecting complements (Two Sum pattern), and caching seen values. In C#, use Dictionary<K,V> for maps and HashSet<T> for membership checks.
Greedy algorithms make locally optimal choices at each step, hoping to reach a global optimum. Greedy works when a problem has the "greedy choice property" and "optimal substructure". Common applications: interval scheduling, activity selection, Huffman coding, and jump game.
// Approach: Map each element to remainder mod value; find smallest integer with no fully-filled bucket.
// Time: O(n) Space: O(value)
public class Solution
{
public int FindSmallestInteger(int[] nums, int value)
{
Dictionary<int, int> count = new Dictionary<int, int>();
foreach (var num in nums)
{
int key = (num % value + value) % value;
if (count.ContainsKey(key))
count[key]++;
else
count[key] = 1;
}
for (int i = 0; i < nums.Length; ++i)
{
if (!count.ContainsKey(i % value) || count[i % value] == 0)
return i;
count[i % value]--;
}
return nums.Length;
}
}