Smallest Missing Non-negative Integer After Operations

Medium
858.

Smallest Missing Non-negative Integer After Operations

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.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} value
 * @return {number}
 */
var findSmallestInteger = function(nums, value) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

  1. Hint 1

    Adding or subtracting value never changes an element's residue modulo value.

  2. Hint 2

    So an element can become exactly the non-negative integers sharing its residue: r, r + value, r + 2·value, …

  3. 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

  1. Tally cnt[r], the number of elements with residue r (normalised to be non-negative).
  2. Walk i = 0, 1, 2, …; the integer i needs an element of residue i % value.
  3. 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

Java

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