Watch 10 video solutions for Smallest Missing Non-negative Integer After Operations, a medium level problem involving Array, Hash Table, Math. This walkthrough by codestorywithMIK has 8,279 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 0-indexed integer array nums and an integer value.
In one operation, you can add or subtract value from any element of nums.
nums = [1,2,3] and value = 2, you can choose to subtract value from nums[0] to make nums = [-1,2,3].The MEX (minimum excluded) of an array is the smallest missing non-negative integer in it.
[-1,2,3] is 0 while the MEX of [1,0,3] is 2.Return the maximum MEX of nums after applying the mentioned operation any number of times.
Example 1:
Input: nums = [1,-10,7,13,6,8], value = 5 Output: 4 Explanation: One can achieve this result by applying the following operations: - Add value to nums[1] twice to make nums = [1,0,7,13,6,8] - Subtract value from nums[2] once to make nums = [1,0,2,13,6,8] - Subtract value from nums[3] twice to make nums = [1,0,2,3,6,8] The MEX of nums is 4. It can be shown that 4 is the maximum MEX we can achieve.
Example 2:
Input: nums = [1,-10,7,13,6,8], value = 7 Output: 2 Explanation: One can achieve this result by applying the following operation: - subtract value from nums[2] once to make nums = [1,-10,0,13,6,8] The MEX of nums is 2. It can be shown that 2 is the maximum MEX we can achieve.
Constraints:
1 <= nums.length, value <= 105-109 <= nums[i] <= 109Problem Overview: You are given an integer array nums and a value value. You can repeatedly add or subtract value from any element. After performing any number of operations, determine the smallest non‑negative integer that cannot appear in the array.
The key observation is that adding or subtracting value does not change an element's remainder modulo value. Every number can only move within its remainder class. The goal becomes distributing elements across remainder buckets so you can form the sequence 0, 1, 2, ... as long as possible.
Approach 1: HashSet and Modulo Arithmetic (O(n) time, O(value) space)
Compute the remainder num % value for each element and store counts for each remainder bucket. To construct the smallest missing integer, iterate from i = 0 upward. Each target integer i requires an element with remainder i % value. If the corresponding bucket still has available elements, consume one and continue. If the bucket is empty, i cannot be formed and is the answer. This greedy process works because any element with the same remainder can be shifted by multiples of value to reach the required number. The algorithm performs a single pass to count remainders and another linear scan to find the missing value, giving O(n) time with O(value) extra space. This approach heavily relies on hash table counting and modular reasoning.
Approach 2: Direct Simulation with Sorting (O(n log n) time, O(1) extra space)
Sort the array first, then try to greedily build the sequence of non‑negative integers starting from 0. For each required target value, scan the sorted array to find an element whose remainder matches target % value. When such an element is used, adjust it conceptually using multiples of value so it becomes the required target. If no suitable element exists, the target is the smallest missing integer. Sorting simplifies searching but increases runtime to O(n log n). This method is easier to reason about during initial problem exploration and works well in languages like C or C++ where direct simulation with arrays is convenient. It demonstrates a greedy build‑up strategy using arrays and greedy allocation.
Recommended for interviews: The modulo frequency approach. Interviewers expect you to recognize that the operation preserves remainders. Building the sequence using remainder buckets shows strong understanding of modular arithmetic and greedy allocation. The simulation approach is acceptable as a stepping stone, but the O(n) remainder counting solution demonstrates deeper insight and scales better for large inputs.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashSet and Modulo Arithmetic | O(n) | O(value) | Best general solution. Uses remainder buckets to greedily construct 0,1,2,... |
| Direct Simulation with Sorting | O(n log n) | O(1) | Useful when starting with a simple idea or when sorting simplifies reasoning |