#2598

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Smallest Missing Non-negative Integer After Operations

Find the smallest missing non-negative integer after repeated additions or subtractions of a given value in nums array efficiently.

array hash table math greedy

Problem Statement

Given a 0-indexed integer array nums and an integer value, you can repeatedly add or subtract value from any element. Your task is to compute the smallest non-negative integer missing from nums after any sequence of operations.

The MEX (minimum excluded) of an array is defined as the smallest non-negative integer not present in the array. Determine the MEX achievable using these operations and provide it as the output.

Examples

Example 1

Input: nums = [1,-10,7,13,6,8], value = 5

Output: 4

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

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 <= 105
-109 <= nums[i] <= 109

Solution Approach

Map numbers modulo value

Use a hash map to track the frequency of each number modulo value. This reduces the problem to counting how many times each remainder can appear after operations, ensuring we consider only achievable numbers for MEX.

Scan sequentially for MEX

Iterate from 0 upwards, using the modulo map to check if each integer can be constructed. Stop at the first integer that cannot be formed, which is the smallest missing number.

Use modular arithmetic and greedy counting

For each remainder, calculate how many times numbers with that remainder can occur. Apply a greedy approach to fill the sequence from 0 onwards, guaranteeing the first unfillable number is the correct MEX.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + value) due to scanning nums and checking counts for each remainder. Space complexity is O(value) for storing remainder frequencies in a hash map.

What Interviewers Usually Probe

Notice how repeated additions and subtractions reduce to modular arithmetic.
Watch for large negative numbers; handle mapping modulo correctly.
Think about a greedy sequential scan to identify the first missing integer efficiently.

Common Pitfalls or Variants

Common pitfalls

Failing to handle negative numbers correctly when computing modulo.
Assuming numbers outside initial array cannot become smaller after operations.
Iterating without counting remainders can lead to incorrect MEX computation.

Follow-up variants

Compute largest reachable number with repeated add/subtract operations.
Find MEX after performing operations only on a subset of array indices.
Determine MEX when each number has a distinct operation value instead of a single value.

FAQ

What pattern does this problem follow?

It follows array scanning plus hash lookup with modular arithmetic to efficiently find the smallest missing number.

How do negative numbers affect the computation?

Negatives should be mapped modulo value correctly to count achievable numbers; otherwise MEX may be computed incorrectly.

Is it necessary to simulate every possible operation?

No, using modular arithmetic and remainder counts allows determining the MEX without exhaustive simulation.

Can this method handle large arrays?

Yes, the hash map approach scales to arrays of length up to 10^5, avoiding O(n^2) operation simulations.

How does GhostInterview solve 'Smallest Missing Non-negative Integer After Operations'?

It tracks remainders, performs a sequential greedy scan, and outputs the correct MEX with optimized modular counting.

terminal

Solution

Solution 1: Counting

We use a hash table $\textit{cnt}$ to count the number of remainders when each number in the array is modulo $\textit{value}$.

1

2

3

4

5

6

7

class Solution:
    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

Continue Practicing

#3588 find maximum area of a triangle #2597 the number of beautiful subsets #2601 prime subtraction operation