Smallest Missing Non-negative Integer After Operations — Medium Problem & Solution

You may repeatedly pick any index and add or subtract value from nums[i], as many times as you like.

Difficulty: Medium
Topics: Arrays, Math, Hash Table, 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

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 residue r (normalised to be non-negative).
Walk i = 0, 1, 2, …; the integer i needs an element of residue i % value.
The first i whose 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 % 5 is 0 but -10 % 7 is -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 += 1

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue