Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Adding or subtracting value preserves a number's remainder, and can reach any integer with that same remainder. To maximize the minimum excluded nonnegative integer, fill targets in increasing order, consuming one available number from the target's remainder class.

Approach

Count normalized remainders of all inputs modulo value, including negative numbers. Starting at zero, check the current target's remainder. If no count remains, return that target: every smaller target can be formed, but this one cannot. Otherwise decrement the count and advance the target. Each element is consumed at most once, and saving a matching element for a later target cannot improve the first missing value.

class Solution:
    def findSmallestInteger(self, nums: List[int], value: int) -> int:
        fm = defaultdict(int)

        for n in nums:
            fm[n % value] += 1

        n = 0
        while True:
            if fm[n % value] == 0:
                return n
            fm[n % value] -= 1
            n += 1

Complexity analysis

Let n = nums.length and v = value. Time: O(n) expected for remainder counting and consuming at most n + 1 candidates. Auxiliary space: O(min(n, v)) for nonzero remainder frequencies.