2598. Smallest Missing Non-negative Integer After Operations LeetCode Solution

In this guide, you will get 2598. Smallest Missing Non-negative Integer After Operations LeetCode Solution with the best time and space complexity. The solution to Smallest Missing Non-negative Integer After Operations problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Smallest Missing Non-negative Integer After Operations solution in C++
4. Smallest Missing Non-negative Integer After Operations solution in Java
5. Smallest Missing Non-negative Integer After Operations solution in Python
6. Additional Resources

Problem Statement of Smallest Missing Non-negative Integer After Operations

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

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(n)

2598. Smallest Missing Non-negative Integer After Operations LeetCode Solution in C++

class Solution {
 public:
  int findSmallestInteger(vector<int>& nums, int value) {
    unordered_map<int, int> count;

    for (const int num : nums)
      ++count[(num % value + value) % value];

    for (int i = 0; i < nums.size(); ++i)
      if (--count[i % value] < 0)
        return i;

    return nums.size();
  }
};
/* code provided by PROGIEZ */

2598. Smallest Missing Non-negative Integer After Operations LeetCode Solution in Java

class Solution {
  public int findSmallestInteger(int[] nums, int value) {
    Map<Integer, Integer> count = new HashMap<>();

    for (final int num : nums)
      count.merge((num % value + value) % value, 1, Integer::sum);

    for (int i = 0; i < nums.length; ++i) {
      if (count.getOrDefault(i % value, 0) == 0)
        return i;
      count.merge(i % value, -1, Integer::sum);
    }

    return nums.length;
  }
}
// code provided by PROGIEZ

2598. Smallest Missing Non-negative Integer After Operations LeetCode Solution in Python

class Solution:
  def findSmallestInteger(self, nums: list[int], value: int) -> int:
    count = collections.Counter([num % value for num in nums])

    for i in range(len(nums)):
      if count[i % value] == 0:
        return i
      count[i % value] -= 1

    return len(nums)
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.