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.
This approach leverages the modulo operation to reduce the problem complexity. By taking each element in nums and calculating the modulo with value, we effectively group numbers into equivalence classes. These classes help identify which remainders exist and which don't. After processing the remainders, MEX is determined by scanning for the first missing number that can't be represented with the available remainders.
The solution iterates over each number, reduces it modulo value, and collects the remainders in a set. Then, it starts from zero and increments until it finds the first missing number, representing the MEX. The use of set ensures the operation is efficient, providing constant time complexity for insertions and lookups.
Time Complexity: O(n), where n is the length of nums since we loop over the list and perform constant time set operations.
Space Complexity: O(min(n, value)), capturing at most value distinct remainders.
This approach sorts the transformed numbers first and then directly derives the MEX by identifying the first break in sequence from zero. By normalizing the numbers and sorting, sequential order becomes apparent, facilitating the determination of MEX.
The implementation modifies each number by normalizing it to a positive range using modulo and ensures all are non-negative by adding value before a second mod operation. After sorting the list, it linear scans to determine the smallest missing integer, i.e., the MEX.
Time Complexity: O(n log n) due to the sort operation.
Space Complexity: O(1) if sorting is done in place; otherwise O(n).
We use a hash table cnt to count the number of remainders when each number in the array is modulo value.
Then we traverse starting from 0. For the current number i being traversed, if cnt[i bmod value] is 0, it means there is no number in the array whose remainder when modulo value is i, so i is the MEX of the array, and we can return it directly. Otherwise, we decrement cnt[i bmod value] by 1 and continue traversing.
The time complexity is O(n) and the space complexity is O(value), where n is the length of array nums.
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Approach Using HashSet and Modulo Arithmetic | Time Complexity: O(n), where n is the length of |
| Approach Using Direct Simulation and Sorting | Time Complexity: O(n log n) due to the sort operation. |
| Counting | — |
| 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 |
Smallest Missing Non-negative Integer After Operations | Simple observation | Leetcode 2598 | MIK • codestorywithMIK • 8,279 views views
Watch 9 more video solutions →Practice Smallest Missing Non-negative Integer After Operations with our built-in code editor and test cases.
Practice on FleetCode