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.
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.
[-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] <= 109This 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.
Java
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.
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.
C
Time Complexity: O(n log n) due to the sort operation.
Space Complexity: O(1) if sorting is done in place; otherwise O(n).
| Approach | Complexity |
|---|---|
| Approach Using HashSet and Modulo Arithmetic | Time Complexity: O(n), where n is the length of |
| Approach Using Direct Simulation and Sorting | Time Complexity: O(n log n) due to the sort operation. |
First Missing Positive - Leetcode 41 - Python • NeetCode • 127,459 views views
Watch 9 more video solutions →Practice Smallest Missing Non-negative Integer After Operations with our built-in code editor and test cases.
Practice on FleetCode