LeetCode 2598. Smallest Missing Non-negative Integer After Operations Solution in Java, C++, Python & More | Explanation + Code

Description

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

Solutions

Solution 1: 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.

PythonJavaC++GoTypeScriptRustJavaScript

class Solution: def findSmallestInteger(self, nums: List[int], value: int) -> int: cnt = Counter(x % value for x in nums) for i in range(len(nums) + 1): if cnt[i % value] == 0: return i cnt[i % value] -= 1(code-box)

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; } } } }(code-box)

class Solution { public: int findSmallestInteger(vector<int>& nums, int value) { int cnt[value]; memset(cnt, 0, sizeof(cnt)); for (int x : nums) { ++cnt[(x % value + value) % value]; } for (int i = 0;; ++i) { if (cnt[i % value]-- == 0) { return i; } } } };(code-box)

func findSmallestInteger(nums []int, value int) int { cnt := make([]int, value) for _, x := range nums { cnt[(x%value+value)%value]++ } for i := 0; ; i++ { if cnt[i%value] == 0 { return i } cnt[i%value]-- } }(code-box)

function findSmallestInteger(nums: number[], value: number): number { const cnt: number[] = new Array(value).fill(0); for (const x of nums) { ++cnt[((x % value) + value) % value]; } for (let i = 0; ; ++i) { if (cnt[i % value]-- === 0) { return i; } } }(code-box)

impl Solution { pub fn find_smallest_integer(nums: Vec<i32>, value: i32) -> i32 { let mut cnt = vec![0; value as usize]; for &x in &nums { let idx = ((x % value + value) % value) as usize; cnt[idx] += 1; } let mut i = 0; loop { let idx = (i % value) as usize; if cnt[idx] == 0 { return i; } cnt[idx] -= 1; i += 1; } } }(code-box)

/** * @param {number[]} nums * @param {number} value * @return {number} */ var findSmallestInteger = function (nums, value) { const cnt = Array(value).fill(0); for (const x of nums) { ++cnt[((x % value) + value) % value]; } for (let i = 0; ; ++i) { if (cnt[i % value]-- === 0) { return i; } } };(code-box)