Smallest Missing Non-negative Integer After Operations

Med

#2378Time: O(N^2), where N is the length of `nums`. The outer `while` loop can run up to N times. Inside the loop, both searching and removing an element from an `ArrayList` take O(K) time, where K is the current size of the list. In the worst case, this is O(N), leading to a total complexity of O(N*N).Space: O(N), where N is the length of `nums`. An auxiliary list `remainders` is created to store the remainders of all N elements.3 companies

Patterns

Math Greedy

Data structures

Array Hash Table

Companies

Atlassian IBM Mercari

Prompt

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.

For example, if 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.

For example, the MEX of [-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 <= 10⁵
-10⁹ <= nums[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process of forming the target sequence 0, 1, 2, .... It first converts all numbers to their base remainders modulo value and then, for each target number k, it searches the entire list of available remainders to see if k % value can be found. If found, the remainder is consumed, and the process continues to k+1.

Algorithm

Create a new ArrayList called remainders.
Iterate through nums and for each num, add its non-negative remainder (num % value + value) % value to the remainders list.
Initialize mex = 0.
Start an infinite loop.
In the loop, search for the value mex % value within the remainders list.
If it is found, remove one occurrence of it from the list and increment mex.
If it is not found, the current mex cannot be formed, so break the loop.
Return the final mex value.

Walkthrough

The fundamental insight is that a number num can be transformed into any other number num' if and only if they share the same remainder when divided by value (i.e., num ≡ num' (mod value)). This is because any operation adds or subtracts a multiple of value, which does not change the remainder.

This approach leverages this by first creating a list of the non-negative remainders of all numbers in the input nums array. Then, it attempts to greedily construct the sequence of non-negative integers starting from 0. It checks for mex = 0, then mex = 1, and so on. To check if a given mex can be formed, it scans the list of remainders to find an element equal to mex % value. If such an element is found, it's removed from the list (to signify it has been used), and the mex is incremented. The process stops when a required remainder is not found in the list. The current value of mex is then the smallest missing non-negative integer that cannot be formed, which is the answer.

1import java.util.ArrayList;2import java.util.List;3 4class Solution {5    public int smallestEqualValue(int[] nums, int value) {6        List<Integer> remainders = new ArrayList<>();7        for (int num : nums) {8            remainders.add((num % value + value) % value);9        }10 11        int mex = 0;12        while (true) {13            int targetRemainder = mex % value;14            // .remove(Object) is O(N), so this loop is N*N15            if (remainders.remove(Integer.valueOf(targetRemainder))) {16                mex++;17            } else {18                break;19            }20        }21        return mex;22    }23}

Complexity

Time

O(N^2), where N is the length of `nums`. The outer `while` loop can run up to N times. Inside the loop, both searching and removing an element from an `ArrayList` take O(K) time, where K is the current size of the list. In the worst case, this is O(N), leading to a total complexity of O(N*N).

Space

O(N), where N is the length of `nums`. An auxiliary list `remainders` is created to store the remainders of all N elements.

Trade-offs

Pros

Conceptually simple to understand.
Directly simulates the process of finding and using numbers.

Cons

Inefficient for large inputs due to the quadratic time complexity.
Repeatedly scanning and modifying the list is slow.

This efficient approach avoids the costly repeated searches by pre-calculating the frequencies of all possible remainders (0 to value-1). By storing these counts in an array, we can check for the availability of a required remainder in constant time, leading to a linear time solution.

Algorithm

Create an integer array counts of size value and initialize it with zeros.
Iterate through the nums array. For each num, calculate its non-negative remainder r = (num % value + value) % value and increment counts[r].
Initialize mex = 0.
Use a while loop that continues as long as we have numbers for the current mex. The condition is counts[mex % value] > 0.
Inside the loop, decrement counts[mex % value] to use up one number, and then increment mex.
The loop terminates when counts[mex % value] is 0, meaning mex cannot be formed. Return mex.

Walkthrough

This approach is based on the same core principle: we need to form the sequence 0, 1, 2, ..., and to form a number k, we need an original number from nums whose remainder modulo value is k % value.

The key optimization is to count the occurrences of each remainder in a single pass. We use an auxiliary array, counts, of size value. counts[r] stores how many numbers in nums have a remainder of r.

After populating this frequency map, we can determine the maximum MEX. We iterate mex from 0 upwards. For each mex, we find the required remainder r = mex % value. We then check our counts array at index r. If counts[r] is greater than zero, it means we have a number we can use. We decrement counts[r] (to mark it as used) and increment mex to try to form the next integer. If counts[r] is zero, we lack the necessary number to form mex, so mex is our answer. This check is an O(1) operation, making the entire process very fast.

1class Solution {2    public int smallestEqualValue(int[] nums, int value) {3        int[] counts = new int[value];4        for (int num : nums) {5            int remainder = (num % value + value) % value;6            counts[remainder]++;7        }8 9        int mex = 0;10        while (counts[mex % value] > 0) {11            counts[mex % value]--;12            mex++;13        }14        15        return mex;16    }17}

Complexity

Time

O(N + value), where N is the length of `nums`. Initializing the `counts` array takes O(value). Populating it takes O(N). The final `while` loop to find the MEX runs at most N+1 times (as `mex` can't exceed N), and each step is an O(1) array access. Thus, the total time is O(N + value).

Space

O(value). We use an auxiliary array `counts` of size `value` to store the frequencies of the remainders.

Trade-offs

Pros

Highly efficient with a linear time complexity of O(N + value).
Simple and clean implementation.

Cons

Requires O(value) extra space, which could be significant if value is very large.

Solutions

Solution

1class Solution {2public3  int findSmallestInteger(int[] nums, int value) {4    int[] cnt = new int[value];5    for (int x : nums) {6      ++cnt[(x % value + value) % value];7    }8    for (int i = 0;; ++i) {9      if (cnt[i % value]-- == 0) {10        return i;11      }12    }13  }14}

1class Solution {2public:3  int findSmallestInteger(vector<int> &nums, int value) {4    int cnt[value];5    memset(cnt, 0, sizeof(cnt));6    for (int x : nums) {7      ++cnt[(x % value + value) % value];8    }9    for (int i = 0;; ++i) {10      if (cnt[i % value]-- == 0) {11        return i;12      }13    }14  }15};

1class Solution:2    def findSmallestInteger(self, nums: List[int], value: int) -> int: cnt = Counter(x % value for x in nums) for i in range(len(nums) + 1): if cnt[i % value] == 0: return i cnt[i % value] -= 1

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem