Scale Engineer

Smallest Missing Non-negative Integer After Operations

Med
#2378Time: O(N^2), where N is the length of `nums`. The outer `while` loop can run up to N times. Inside the loop, both searching and removing an element from an `ArrayList` take O(K) time, where K is the current size of the list. In the worst case, this is O(N), leading to a total complexity of O(N*N).Space: O(N), where N is the length of `nums`. An auxiliary list `remainders` is created to store the remainders of all N elements.3 companies
Patterns
MathGreedy
Data structures
ArrayHash Table
Companies
AtlassianIBMMercari

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process of forming the target sequence 0, 1, 2, .... It first converts all numbers to their base remainders modulo value and then, for each target number k, it searches the entire list of available remainders to see if k % value can be found. If found, the remainder is consumed, and the process continues to k+1.

Algorithm

  • Create a new ArrayList called remainders.
  • Iterate through nums and for each num, add its non-negative remainder (num % value + value) % value to the remainders list.
  • Initialize mex = 0.
  • Start an infinite loop.
  • In the loop, search for the value mex % value within the remainders list.
  • If it is found, remove one occurrence of it from the list and increment mex.
  • If it is not found, the current mex cannot be formed, so break the loop.
  • Return the final mex value.

Walkthrough

The fundamental insight is that a number num can be transformed into any other number num' if and only if they share the same remainder when divided by value (i.e., num ≡ num' (mod value)). This is because any operation adds or subtracts a multiple of value, which does not change the remainder.

This approach leverages this by first creating a list of the non-negative remainders of all numbers in the input nums array. Then, it attempts to greedily construct the sequence of non-negative integers starting from 0. It checks for mex = 0, then mex = 1, and so on. To check if a given mex can be formed, it scans the list of remainders to find an element equal to mex % value. If such an element is found, it's removed from the list (to signify it has been used), and the mex is incremented. The process stops when a required remainder is not found in the list. The current value of mex is then the smallest missing non-negative integer that cannot be formed, which is the answer.

import java.util.ArrayList;import java.util.List; class Solution {    public int smallestEqualValue(int[] nums, int value) {        List<Integer> remainders = new ArrayList<>();        for (int num : nums) {            remainders.add((num % value + value) % value);        }         int mex = 0;        while (true) {            int targetRemainder = mex % value;            // .remove(Object) is O(N), so this loop is N*N            if (remainders.remove(Integer.valueOf(targetRemainder))) {                mex++;            } else {                break;            }        }        return mex;    }}

Complexity

Time

O(N^2), where N is the length of `nums`. The outer `while` loop can run up to N times. Inside the loop, both searching and removing an element from an `ArrayList` take O(K) time, where K is the current size of the list. In the worst case, this is O(N), leading to a total complexity of O(N*N).

Space

O(N), where N is the length of `nums`. An auxiliary list `remainders` is created to store the remainders of all N elements.

Trade-offs

Pros

  • Conceptually simple to understand.

  • Directly simulates the process of finding and using numbers.

Cons

  • Inefficient for large inputs due to the quadratic time complexity.

  • Repeatedly scanning and modifying the list is slow.

Solutions

class Solution {public  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) {      if (cnt[i % value]-- == 0) {        return i;      }    }  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem