2598. Smallest Missing Non-negative Integer After Operations
Problem Description
This problem presents an optimization challenge with a combination of array manipulation and a novel concept called MEX (minimum excluded), which represents the smallest non-negative integer not present in the array. We are given an array nums
and an integer value
. The operation at our disposal allows us to add or subtract value
from any element in nums
. The goal is to apply this operation as many times as we want to maximize the MEX of the resulting array.
Understanding the MEX is crucial as it is the key evaluation metric for the outcome of array manipulations. For instance, in an array [-1, 2, 3]
, since 0
and 1
are not present, the MEX is 0
, as it is the smallest non-negative integer not in the array. However, if we had [1, 0, 3]
, the MEX would be 2
. What makes this problem interesting is the strategic decision of how to add or subtract 'value' in order to maximize the MEX.
Intuition
To solve the problem, we need a smart way to track the potential MEX without exhaustively enumerating all possible permutations of array changes, which would be computationally infeasible. The intuition here lies in realizing that adding or subtracting value
doesn't affect the remainder when each element of nums
is divided by value
. Consequently, the remainders form certain 'buckets' that we can only fill up to a certain level - dictated by how many times a remainder appears in the original array.
This leads to the insight that we can use the frequencies of these remainders to determine the MEX without iterating through all possible array operations. Specifically, by initializing a counter for the frequency of each remainder (modulo value
) present in the array, we can iterate from 0
and move up to find the smallest non-negative integer (our potential MEX) that doesn't collide with existing remainder frequencies.
When the counter for a remainder corresponding to i % value
is 0
, it signals that we've hit a 'gap', or a value that can't be created through any combination of operations on the current array, since none of the array elements produce a remainder equal to i % value
when divided by value
. That's our desired maximum MEX. If not, we decrement the count and move to the next integer, repeating the process until we find our MEX.
Solution Approach
The solution strategy is built on a counting approach, which significantly simplifies the operation and determination of MEX. Letās expound on the implementation of the solution:
-
Counting Modulo Frequencies: We realize that the operation of adding or subtracting
value
from any element innums
retains its modulovalue
. Thus, we store the count of occurrences of each remainder after dividing the elements byvalue
using aCounter
data structure. This gives us the frequency distribution of remainders. -
Modulo Value as a Key Insight: We use the modulo operation considering
value
as an invariant in our problem. This insight solves the optimization problem by allowing us to work with a limited number of remainders (from0
tovalue - 1
) and their counts instead of dealing with potentially large numbers after multiple addition or subtraction operations. -
Iterating for MEX: We initialize an iteration from
0
upwards, continuing tolen(nums) + 1
to cover all potential MEX values. In each iteration:-
We check if the count for the current number
i
modulovalue
is0
. If it is, no number innums
can be changed through addition or subtraction operations to get a remainder that matchesi % value
. Hence,i
represents a MEX that cannot be obtained through any variant of thenums
array, and we immediately return it as the maximum MEX. -
If the count is not
0
, it implies thati % value
is a possible remainder and thereby not the MEX. We decrement the count for the remainderi % value
by1
because, conceptually, we have 'used up' one instance where a number in the array could achieve this remainder. We continue to the next iteration to find the MEX.
-
This approach avoids brute-force computation and provides an elegant, efficient path to determining the MEX. We rely on the cyclic nature of modulo operation and the Counters that track the possibility of numbers to be fashioned into a specific modulus bucket through the given operation.
The algorithm is optimized as it avoids iterating through all possible operations on the array and instead, operates on a simple linear search for the smallest non-present modulo within the range, thus optimizing it to a time complexity of O(n).
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution with an example. Consider the array nums = [1, 3, 4]
and let value = 3
. We want to maximize the MEX of the array by adding or subtracting 3
to elements in nums
.
Step 1: Counting Modulo Frequencies
First, we count the modulo frequencies. The remainders of numbers in nums
when divided by value = 3
are:
1 % 3 = 1
3 % 3 = 0
4 % 3 = 1
So, our frequency distribution (remainder counts) is:
- Remainder
0
: 1 occurrence - Remainder
1
: 2 occurrences - Remainder
2
: 0 occurrences
Step 2: Utilizing Modulo Value as an Insight
We acknowledge that we can deal with numbers in nums
only in terms of their remainders when divided by value
.
Step 3: Iterating for MEX
Starting from 0
, we check the remainder counts:
-
For
i = 0
: The remainder0 % 3 = 0
has a count of1
(from the number3
innums
). This is not our MEX, so we decrement the count for remainder0
. -
For
i = 1
: The remainder1 % 3 = 1
has a count of2
. Again, we decrement the count for remainder1
. -
For
i = 2
: The remainder2 % 3 = 2
has a count of0
. This means that we've found a gap here; we can't get a remainder of2
by adding or subtracting3
from any element innums
. Hence, the MEX is2
.
This concludes our example. Without performing any operations on the array nums
, we have efficiently determined that the maximum MEX achievable is 2
by just iterating through remainders and their counts.
Solution Implementation
1from collections import Counter
2from typing import List
3
4class Solution:
5 def findSmallestInteger(self, nums: List[int], value: int) -> int:
6 # Create a counter to keep track of the frequency of each number modulo 'value'
7 modulo_counter = Counter(num % value for num in nums)
8
9 # Iterate over the numbers from 0 to length of nums (inclusive)
10 for i in range(len(nums) + 1):
11 # If there is no number i modulo 'value' in our collection, return i
12 if modulo_counter[i % value] == 0:
13 return i
14 # Otherwise, decrease the count of i modulo 'value' by one
15 modulo_counter[i % value] -= 1
16
1class Solution {
2
3 // Method to find the smallest integer that is not present in the array when modulus with value
4 public int findSmallestInteger(int[] nums, int value) {
5 // Create an array to count occurrences of each modulus result
6 int[] countModulo = new int[value];
7
8 // Iterate over each number in nums and increment the count for the corresponding modulus
9 for (int num : nums) {
10 countModulo[(num % value + value) % value]++;
11 }
12
13 // Start looking for the smallest integer that is not in the array, by checking modulus occurrences
14 for (int i = 0; ; ++i) { // no termination condition here since we are guaranteed to find a number eventually
15 // Use the i % value to wrap around the countModulo array
16 // Check if the current number has a count of zero, which means it's not present in the nums array when modulus with value
17 if (countModulo[i % value] == 0) {
18 // If it's not present, this is the smallest number we are looking for
19 return i;
20 }
21 // Otherwise, decrease the count and keep looking
22 countModulo[i % value]--;
23 }
24 }
25}
26
1#include <vector>
2#include <cstring>
3
4class Solution {
5public:
6 int findSmallestInteger(vector<int>& nums, int value) {
7 // Create an array to count occurrences of each modulus value
8 int countArray[value];
9
10 // Initialize the countArray with zeros
11 memset(countArray, 0, sizeof(countArray));
12
13 // Fill the countArray with the count of each modulus value
14 for (int num : nums) {
15 // Correct negative values using modulo operation, then increment the count
16 ++countArray[(num % value + value) % value];
17 }
18
19 // Iterate to find the smallest integer not present in nums when modulo `value`
20 for (int i = 0; ; ++i) {
21 // Calculate the current index modulo value
22 int modIndex = i % value;
23
24 // If the count for the current index is zero,
25 // it means the integer `i` is not present in nums as mod value
26 if (countArray[modIndex] == 0) {
27 // Return the smallest integer not present
28 return i;
29 }
30
31 // Decrement the count for the current index as it is now being used
32 --countArray[modIndex];
33 }
34 // The loop is designed to run indefinitely, will break internally.
35 }
36};
37
1function findSmallestInteger(nums: number[], value: number): number {
2 // Initialize a counter array with size 'value' and fill it with 0s.
3 const count: number[] = new Array(value).fill(0);
4
5 // Increment the count for each number in nums based on its modulo 'value'
6 for (const num of nums) {
7 const index = ((num % value) + value) % value; // Handles negative numbers
8 count[index]++;
9 }
10
11 // Iterate to find the smallest integer not in 'nums' after modulo 'value'.
12 for (let i = 0; ; ++i) {
13 const index = i % value; // Calculate the index in the count array
14
15 // If the count at the current index is 0, this is the smallest integer not found in 'nums'
16 if (count[index] === 0) {
17 return i;
18 }
19
20 // Otherwise, decrement the count at the current index
21 count[index]--;
22 }
23 // The loop is intended to run indefinitely, as it will always return inside the loop body.
24}
25
Time and Space Complexity
The given Python code defines a method findSmallestInteger
meant to find the smallest integer that is not present in the input list nums
when considering each number modulo value
. It manages this by creating a frequency counter for the modulo results and then iteratively checking for the smallest index that is not present in the frequency counter.
Time Complexity
The time complexity of the function is O(n)
, where n
is the length of the input list nums
. This arises from the following operations:
- Initializing the counter with
(x % value for x in nums)
has a linear runtime proportional to the size ofnums
. - The subsequent for loop runs for
n + 1
iterations in the worst case, as it stops as soon as it finds an integer that is not in the counter. Each operation within the for loop (accessingcnt
and decrementing the count) isO(1)
thanks to Python'sCounter
which is a hash map under the hood.
Therefore, as the initialization of the counter and the for loop are both linear in terms of n
and are not nested, the overall time complexity remains linear or O(n)
.
Space Complexity
The space complexity of the algorithm is O(value)
, where value
is the input parameter to the method. This complexity is attributed to the following points:
- The counter
cnt
stores at mostvalue
different keys, since each number innums
is taken modulovalue
, which results in a possible range of[0, value)
. - No other data structures are used that depend on the size of the input or
value
.
Thus, the space required by the counter is directly proportional to the value
, leading to a space complexity of O(value)
.
Learn more about how to find time and space complexity quickly using problem constraints.
How does merge sort divide the problem into subproblems?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!