How to Solve Smallest Missing Non-negative Integer After Operations

This problem asks for the smallest non-negative integer not present after performing any number of add or subtract operations with a fixed value on elements. The solution relies on modular arithmetic to categorize numbers and count achievable remainders, then scans sequentially to determine the MEX. Efficient use of a hash map avoids repeated operations and ensures correct computation even for large arrays.

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

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.

How GhostInterview Helps

• Automatically tracks remainder frequencies and simulates greedy scan for MEX.
• Highlights edge cases with negatives and large gaps in the array.
• Generates example sequences showing why a particular MEX is achievable or blocked.

Topic Pages

• Array
• Hash Table
• Math
• Greedy

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.