Smallest Missing Non-negative Integer After Operations Solution
Smallest Missing Non-negative Integer After Operations solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Smallest Missing Non-negative Integer After Operations is a medium coding problem on arrays, hash table and math, asked in Amazon, Google and Atlassian interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Math, Greedy, Counting
- Asked at: Amazon, Google, Atlassian
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You may repeatedly pick any index and add or subtract value from nums[i], as many times as you like.
The MEX of an array is the smallest non-negative integer missing from it. Return the maximum MEX achievable.
Example 1
Input: nums = [1,-10,7,13,6,8], value = 5
Output: 4
Explanation: The residues mod 5 cover 0, 1, 2 and 3, but nothing can become 4.
Example 2
Input: nums = [1,-10,7,13,6,8], value = 7
Output: 2
Explanation: No element has residue 2 mod 7.
Example 3
Input: nums = [3,0,3,2,4,2,1,1,0,4], value = 5
Output: 10
Constraints
1 <= nums.length, value <= 100000-1000000000 <= nums[i] <= 1000000000
Hints for Smallest Missing Non-negative Integer After Operations
Hint 1
Adding or subtracting
valuenever changes an element's residue modulovalue.Hint 2
So an element can become exactly the non-negative integers sharing its residue:
r, r + value, r + 2·value, …Hint 3
Count how many elements sit in each residue class, then walk
0, 1, 2, …spending one from the matching class each time.
How to solve Smallest Missing Non-negative Integer After Operations
The operation preserves residues modulo value, so each element can cover any non-negative integer in its own residue class. Counting the class sizes reduces the problem to walking upwards and spending one element per integer.
Approach
- Tally
cnt[r], the number of elements with residuer(normalised to be non-negative). - Walk
i = 0, 1, 2, …; the integerineeds an element of residuei % value. - The first
iwhose class is exhausted is the answer.
Why it works
Because residues are invariant, an element can be turned into i precisely when i % value matches its residue, and it can serve only one integer. Filling 0, 1, 2, … in order is optimal: an element of class r should go to the smallest unfilled integer of that class, and any other assignment leaves a smaller gap unfilled.
Complexity
- Time —
O(n + answer) - Space —
O(value)
Pitfalls
- In most languages
-10 % 5is0but-10 % 7is-3— the residue needs normalising with((x % v) + v) % v. - The walk is bounded by
n + 1, so it always terminates. - Sorting or searching the values is unnecessary; only the residue counts matter.
Reference solution
Python
from typing import List
def findSmallestInteger(nums: List[int], value: int) -> int:
cnt = [0] * value
for x in nums:
cnt[x % value] += 1
i = 0
while True:
r = i % value
if cnt[r] == 0:
return i
cnt[r] -= 1
i += 1Java
public static int findSmallestInteger(int[] nums, int value) {
int[] cnt = new int[value];
for (int x : nums) cnt[((x % value) + value) % value]++;
for (int i = 0; ; i++) {
int r = i % value;
if (cnt[r] == 0) return i;
cnt[r]--;
}
}C++
int findSmallestInteger(vector<int>& nums, int value) {
vector<int> cnt(value, 0);
for (int x : nums) cnt[((x % value) + value) % value]++;
for (int i = 0; ; i++) {
int r = i % value;
if (cnt[r] == 0) return i;
cnt[r]--;
}
}JavaScript
var findSmallestInteger = function(nums, value) {
var cnt = [];
for (var t = 0; t < value; t++) cnt.push(0);
for (var j = 0; j < nums.length; j++) cnt[((nums[j] % value) + value) % value]++;
for (var i = 0; ; i++) {
var r = i % value;
if (cnt[r] === 0) return i;
cnt[r]--;
}
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets