Skip to main content
Talentd

Smallest Missing Non-negative Integer After Operations - Solution & Explanation

MediumArrayHash TableMathGreedy12 min readAsked at: Amazon, Microsoft, IBM +3
Practice this problem

Problem Statement

You are given a 0-indexed integer array nums and an integer value.

In one operation, you can add or subtract value from any element of nums.

  • For example, if nums = [1,2,3] and value = 2, you can choose to subtract value from nums[0] to make nums = [-1,2,3].

The MEX (minimum excluded) of an array is the smallest missing non-negative integer in it.

  • For example, the MEX of [-1,2,3] is 0 while the MEX of [1,0,3] is 2.

Return the maximum MEX of nums after applying the mentioned operation any number of times.

 

Example 1:

Input: nums = [1,-10,7,13,6,8], value = 5
Output: 4
Explanation: 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
Explanation: 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

Approach Overview

Problem Overview: You are given an integer array nums and a value value. You can repeatedly add or subtract value from any element. After performing any number of operations, determine the smallest non‑negative integer that cannot appear in the array.

The key observation is that adding or subtracting value does not change an element's remainder modulo value. Every number can only move within its remainder class. The goal becomes distributing elements across remainder buckets so you can form the sequence 0, 1, 2, ... as long as possible.

Approach 1: HashSet and Modulo Arithmetic (O(n) time, O(value) space)

Compute the remainder num % value for each element and store counts for each remainder bucket. To construct the smallest missing integer, iterate from i = 0 upward. Each target integer i requires an element with remainder i % value. If the corresponding bucket still has available elements, consume one and continue. If the bucket is empty, i cannot be formed and is the answer. This greedy process works because any element with the same remainder can be shifted by multiples of value to reach the required number. The algorithm performs a single pass to count remainders and another linear scan to find the missing value, giving O(n) time with O(value) extra space. This approach heavily relies on hash table counting and modular reasoning.

Approach 2: Direct Simulation with Sorting (O(n log n) time, O(1) extra space)

Sort the array first, then try to greedily build the sequence of non‑negative integers starting from 0. For each required target value, scan the sorted array to find an element whose remainder matches target % value. When such an element is used, adjust it conceptually using multiples of value so it becomes the required target. If no suitable element exists, the target is the smallest missing integer. Sorting simplifies searching but increases runtime to O(n log n). This method is easier to reason about during initial problem exploration and works well in languages like C or C++ where direct simulation with arrays is convenient. It demonstrates a greedy build‑up strategy using arrays and greedy allocation.

Recommended for interviews: The modulo frequency approach. Interviewers expect you to recognize that the operation preserves remainders. Building the sequence using remainder buckets shows strong understanding of modular arithmetic and greedy allocation. The simulation approach is acceptable as a stepping stone, but the O(n) remainder counting solution demonstrates deeper insight and scales better for large inputs.

Approach 1: Approach Using HashSet and Modulo Arithmetic

This approach leverages the modulo operation to reduce the problem complexity. By taking each element in nums and calculating the modulo with value, we effectively group numbers into equivalence classes. These classes help identify which remainders exist and which don't. After processing the remainders, MEX is determined by scanning for the first missing number that can't be represented with the available remainders.

The solution iterates over each number, reduces it modulo value, and collects the remainders in a set. Then, it starts from zero and increments until it finds the first missing number, representing the MEX. The use of set ensures the operation is efficient, providing constant time complexity for insertions and lookups.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n), where n is the length of nums since we loop over the list and perform constant time set operations.
Space Complexity: O(min(n, value)), capturing at most value distinct remainders.

Try this approach in the editor →

Approach 2: Approach Using Direct Simulation and Sorting

This approach sorts the transformed numbers first and then directly derives the MEX by identifying the first break in sequence from zero. By normalizing the numbers and sorting, sequential order becomes apparent, facilitating the determination of MEX.

The implementation modifies each number by normalizing it to a positive range using modulo and ensures all are non-negative by adding value before a second mod operation. After sorting the list, it linear scans to determine the smallest missing integer, i.e., the MEX.

Code

C++C

C++

C

Complexity

Time Complexity: O(n log n) due to the sort operation.
Space Complexity: O(1) if sorting is done in place; otherwise O(n).

Try this approach in the editor →

Approach 3: Counting

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

Then we traverse starting from 0. For the current number i being traversed, if cnt[i bmod value] is 0, it means there is no number in the array whose remainder when modulo value is i, so i is the MEX of the array, and we can return it directly. Otherwise, we decrement cnt[i bmod value] by 1 and continue traversing.

The time complexity is O(n) and the space complexity is O(value), where n is the length of array nums.

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach Using HashSet and Modulo Arithmetic

Time Complexity: O(n), where n is the length of nums since we loop over the list and perform constant time set operations.
Space Complexity: O(min(n, value)), capturing at most value distinct remainders.

Approach Using Direct Simulation and Sorting

Time Complexity: O(n log n) due to the sort operation.
Space Complexity: O(1) if sorting is done in place; otherwise O(n).

Counting—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashSet and Modulo ArithmeticO(n)O(value)Best general solution. Uses remainder buckets to greedily construct 0,1,2,...
Direct Simulation with SortingO(n log n)O(1)Useful when starting with a simple idea or when sorting simplifies reasoning

Video Solution

Smallest Missing Non-negative Integer After Operations | Simple observation | Leetcode 2598 | MIK • codestorywithMIK • 8,391 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Smallest Missing Non-negative Integer After Operations easy or hard?
The problem is rated Medium on LeetCode. The implementation is straightforward once the key insight is discovered: operations preserve the remainder modulo value. Recognizing this transformation from value manipulation to remainder counting is the main challenge.
Smallest Missing Non-negative Integer After Operations Python/Java solution
Python and Java implementations usually use a dictionary or array to store counts of num % value. After computing frequencies, iterate from 0 upward and consume counts for remainder i % value until a remainder bucket becomes empty. The integer where this happens is the answer.
How to solve Smallest Missing Non-negative Integer After Operations in O(n)?
Compute remainder frequencies for num % value. Then iterate integers starting from 0. For each integer i, check the bucket i % value. If a number exists in that bucket, decrement its count and continue. If the bucket is empty, i cannot be formed using allowed operations and is the smallest missing integer.
What is the best approach for Smallest Missing Non-negative Integer After Operations?
The optimal solution uses modulo frequency counting. Since adding or subtracting the given value does not change an element's remainder modulo value, numbers are grouped by remainder. Greedily try to construct integers starting from 0 and consume elements from the corresponding remainder bucket. This runs in O(n) time with O(value) extra space.
Is Smallest Missing Non-negative Integer After Operations asked at Google/Amazon/Meta?
Problems involving modular grouping, greedy construction, and missing integers frequently appear in interviews at companies like Google, Amazon, and Meta. This specific LeetCode problem is considered medium difficulty and tests reasoning about modular arithmetic and hash table counting.
What data structure is used in Smallest Missing Non-negative Integer After Operations?
The most common structure is a hash table or frequency array that counts how many elements fall into each remainder bucket modulo value. This allows constant-time lookup when determining whether a required remainder is available while constructing the sequence of integers.
What is the time complexity of Smallest Missing Non-negative Integer After Operations?
The optimal approach runs in O(n) time. One pass counts how many numbers belong to each remainder class modulo value, and another pass greedily checks integers starting from 0. The space complexity is O(value) for storing remainder frequencies.

Ready to solve this problem?

Practice Smallest Missing Non-negative Integer After Operations with our built-in code editor and test cases.

Practice on FleetCode
Previous

First Missing Positive