LeetCode 2598 - Smallest Missing Non-negative Integer After Operations
That is a long, structured technical guide with multiple required sections and two full implementations. To keep the quality high and follow your formatting rules exactly, I will provide it in a single comprehensive response.
Difficulty: š” Medium
Topics: Array, Hash Table, Math, Greedy
Solution
That is a long, structured technical guide with multiple required sections and two full implementations. To keep the quality high and follow your formatting rules exactly, I will provide it in a single comprehensive response.
LeetCode 2598 - Smallest Missing Non-negative Integer After Operations
Problem Understanding
The problem gives us an integer array nums and an integer value. We are allowed to repeatedly perform an operation on any element of the array: add or subtract value any number of times.
The key observation is that adding or subtracting value does not allow an element to become any arbitrary number. Instead, every number remains in the same remainder class modulo value.
For example, if value = 5:
1can become..., -9, -4, 1, 6, 11, ...7can become..., -3, 2, 7, 12, ...
Notice that all values reachable from 7 have remainder 2 when divided by 5.
The task is to maximize the MEX of the array after applying operations any number of times.
The MEX (Minimum Excluded Value) of an array is the smallest non-negative integer that does not appear in the array.
For example:
[0,1,2,4]has MEX3[1,2,3]has MEX0[0,1,3]has MEX2
Since we can modify the numbers freely using the allowed operation, we want to rearrange the values as effectively as possible to create the longest consecutive sequence starting from 0.
The constraints are important:
nums.length <= 10^5value <= 10^5nums[i]may be very large or negative, up to10^9
These limits immediately rule out brute force simulation of operations. Since values can become extremely large or negative, we cannot literally try all possible transformations.
Instead, we need to exploit the mathematical structure of the operation.
Several edge cases are important:
- Negative numbers, because modulo behavior must be handled carefully.
- Duplicate remainder groups, since multiple numbers may compete for the same target values.
- Very large values of
nums[i], where brute force shifting becomes impossible. - Cases where
value = 1, because every number can transform into any integer.
Approaches
Brute Force Approach
A naive way to think about this problem is to repeatedly try constructing the sequence 0,1,2,... and see whether some element can be transformed into each number.
For every target integer x, we could scan through nums and check whether some unused number can be transformed into x.
A number num can become x if:
(num - x) % value == 0
If we find such a number, we mark it as used and continue to x + 1. Otherwise, x is the MEX.
This method is correct because it explicitly attempts to build the longest consecutive prefix of non-negative integers.
However, it is too slow. For every candidate MEX value, we may scan the whole array. Since the answer itself may be as large as n, the complexity becomes roughly:
O(n^2)
which is too expensive for n = 10^5.
Key Insight
The crucial observation is that adding or subtracting value preserves the modulo class.
If:
x % value == r
then only numbers whose remainder modulo value is also r can transform into x.
This transforms the problem into resource allocation.
Suppose:
value = 5
and we count how many numbers belong to each remainder group.
Example:
nums = [1,-10,7,13,6,8]
Modulo 5:
1 -> 1
-10 -> 0
7 -> 2
13 -> 3
6 -> 1
8 -> 3
Frequency table:
0 -> 1
1 -> 2
2 -> 1
3 -> 2
4 -> 0
Now try building numbers starting from 0.
0needs remainder0, available1needs remainder1, available2needs remainder2, available3needs remainder3, available4needs remainder4, unavailable
So answer is 4.
We do not care which exact numbers are used. We only care how many numbers exist in each remainder bucket.
Approach Comparison
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(nĀ²) | O(n) | Try assigning numbers to every candidate value |
| Optimal | O(n) | O(value) | Count modulo frequencies and greedily consume them |
Algorithm Walkthrough
Optimal Algorithm
- Create a frequency map for remainders modulo
value.
For every number in nums, compute:
remainder = num % value
Since negative modulo behaves differently in some languages, normalize it:
remainder = ((num % value) + value) % value
Store how many numbers belong to each remainder class.
2. Start building the sequence from 0.
Initialize:
current = 0
This represents the next number we are trying to create. 3. Determine which remainder class is needed.
To construct number current, we need a number from:
current % value
- Check availability.
If the frequency for this remainder is zero, we cannot form current.
Since MEX is the first missing non-negative integer, immediately return current.
5. Consume one number from that remainder group.
Decrease its frequency by one because we used one number to represent current.
6. Continue to the next integer.
Increment:
current += 1
- Repeat until a remainder class becomes unavailable.
Why it works
The algorithm works because every integer x can only be formed by numbers with remainder:
x % value
Since operations never change modulo class, the only question is whether we still have an unused number in that class.
Greedily constructing numbers from 0 upward is optimal because MEX depends only on the first missing integer. If we can build x, there is never a reason to delay it in favor of a larger number. Therefore, consuming remainder resources in order guarantees the maximum possible MEX.
Python Solution
from typing import List
from collections import Counter
class Solution:
def findSmallestInteger(self, nums: List[int], value: int) -> int:
remainder_count = Counter()
for num in nums:
remainder = ((num % value) + value) % value
remainder_count[remainder] += 1
current = 0
while True:
required_remainder = current % value
if remainder_count[required_remainder] == 0:
return current
remainder_count[required_remainder] -= 1
current += 1
The implementation begins by counting how many numbers belong to each modulo class. Since a number can only transform into values with the same remainder modulo value, this frequency map captures all useful information.
Next, the algorithm greedily tries to construct integers starting from 0. For each candidate number, it checks whether a number from the required remainder class is still available.
If no number exists in that bucket, the current integer is missing, which means it is the MEX.
Otherwise, one count is consumed and the algorithm moves to the next integer.
The Counter data structure is useful here because it automatically returns 0 for missing keys, avoiding special-case handling.
Go Solution
func findSmallestInteger(nums []int, value int) int {
remainderCount := make(map[int]int)
for _, num := range nums {
remainder := ((num % value) + value) % value
remainderCount[remainder]++
}
current := 0
for {
requiredRemainder := current % value
if remainderCount[requiredRemainder] == 0 {
return current
}
remainderCount[requiredRemainder]--
current++
}
}
The Go implementation follows the same logic as Python but uses a map[int]int instead of Counter.
One important detail is modulo normalization:
((num % value) + value) % value
Go can produce negative modulo results for negative numbers, so normalization ensures remainders always fall in the range:
[0, value - 1]
Unlike Python, Go maps return the zero value for missing keys, so checking:
remainderCount[key] == 0
works naturally.
Worked Examples
Example 1
nums = [1,-10,7,13,6,8]
value = 5
First compute remainders.
| Number | Remainder |
|---|---|
| 1 | 1 |
| -10 | 0 |
| 7 | 2 |
| 13 | 3 |
| 6 | 1 |
| 8 | 3 |
Frequency map:
| Remainder | Count |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 2 | 1 |
| 3 | 2 |
| 4 | 0 |
Now build MEX greedily.
| Current | Required Remainder | Available? | Updated Count |
|---|---|---|---|
| 0 | 0 | Yes | 0 ā 0 |
| 1 | 1 | Yes | 1 ā 1 |
| 2 | 2 | Yes | 2 ā 0 |
| 3 | 3 | Yes | 3 ā 1 |
| 4 | 4 | No | Stop |
Answer:
4
Example 2
nums = [1,-10,7,13,6,8]
value = 7
Remainders:
| Number | Remainder |
|---|---|
| 1 | 1 |
| -10 | 4 |
| 7 | 0 |
| 13 | 6 |
| 6 | 6 |
| 8 | 1 |
Frequency map:
| Remainder | Count |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 4 | 1 |
| 6 | 2 |
Greedy construction:
| Current | Required Remainder | Available? |
|---|---|---|
| 0 | 0 | Yes |
| 1 | 1 | Yes |
| 2 | 2 | No |
Answer:
2
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | One pass to count remainders, one pass to build MEX |
| Space | O(value) | At most value remainder buckets |
The counting phase processes every number once, costing O(n) time.
The greedy construction phase can run at most n + 1 times because each successful step consumes one number from the frequency map. Since there are only n numbers, the loop cannot exceed O(n) iterations.
The frequency map stores at most value unique remainder classes, so auxiliary space is O(value).
Test Cases
from typing import List
s = Solution()
assert s.findSmallestInteger([1, -10, 7, 13, 6, 8], 5) == 4 # example 1
assert s.findSmallestInteger([1, -10, 7, 13, 6, 8], 7) == 2 # example 2
assert s.findSmallestInteger([0], 1) == 1 # single zero
assert s.findSmallestInteger([1], 1) == 0 # cannot form zero
assert s.findSmallestInteger([-1], 2) == 0 # negative number only
assert s.findSmallestInteger([0, 1, 2], 10) == 3 # already consecutive
assert s.findSmallestInteger([100, 200, 300], 1) == 3 # value=1, everything transformable
assert s.findSmallestInteger([0, 0, 0], 1) == 3 # duplicates with value=1
assert s.findSmallestInteger([1, 2, 3], 2) == 2 # mixed remainders
assert s.findSmallestInteger([-5, -10, -15], 5) == 1 # all same remainder
assert s.findSmallestInteger(list(range(100000)), 100000) == 100000 # large input
Test Summary
| Test | Why |
|---|---|
| Example 1 | Validates provided sample |
| Example 2 | Validates second sample |
[0], value=1 |
Smallest valid input |
[1], value=1 |
Missing zero immediately |
[-1], value=2 |
Negative modulo handling |
[0,1,2], value=10 |
Already consecutive |
[100,200,300], value=1 |
All numbers transformable |
[0,0,0], value=1 |
Duplicate consumption |
[1,2,3], value=2 |
Competing remainder groups |
[-5,-10,-15], value=5 |
Same remainder bucket |
| Large sequential array | Stress test for performance |
Edge Cases
One important edge case occurs when value = 1. In this scenario, every number belongs to the same modulo class because all numbers have remainder 0. Since we can add or subtract 1 freely, every element can become any integer. The answer therefore becomes the number of elements in the array. The implementation handles this naturally because all frequencies go into one bucket and get consumed sequentially.
Another important edge case involves negative numbers. Languages such as Go may produce negative modulo values, which can incorrectly place numbers into the wrong remainder group. For example:
-1 % 5 = -1
instead of 4. The implementation avoids this bug using:
((num % value) + value) % value
which guarantees a valid remainder in the range [0, value - 1].
A third important edge case is duplicate remainder classes. Multiple numbers may share the same modulo value and must be used carefully. For example:
nums = [0,0,0]
value = 1
All numbers belong to the same remainder bucket. The greedy algorithm consumes them one at a time to construct:
0,1,2
After the third usage, the bucket becomes empty and the answer correctly becomes 3.
Finally, large input sizes require an efficient solution. Since nums.length can reach 100000, any quadratic algorithm would time out. The implementation avoids repeated scanning and instead uses a hash map for constant time remainder counting, keeping the overall complexity linear.