You are given an integer array nums of length n and a 2D array queries where queries[i] = [li, ri].
Each queries[i] represents the following action on nums:
[li, ri] in nums by at most 1.A Zero Array is an array with all its elements equal to 0.
Return the maximum number of elements that can be removed from queries, such that nums can still be converted to a zero array using the remaining queries. If it is not possible to convert nums to a zero array, return -1.
Example 1:
Input: nums = [2,0,2], queries = [[0,2],[0,2],[1,1]]
Output: 1
Explanation:
After removing queries[2], nums can still be converted to a zero array.
queries[0], decrement nums[0] and nums[2] by 1 and nums[1] by 0.queries[1], decrement nums[0] and nums[2] by 1 and nums[1] by 0.Example 2:
Input: nums = [1,1,1,1], queries = [[1,3],[0,2],[1,3],[1,2]]
Output: 2
Explanation:
We can remove queries[2] and queries[3].
Example 3:
Input: nums = [1,2,3,4], queries = [[0,3]]
Output: -1
Explanation:
nums cannot be converted to a zero array even after using all the queries.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1051 <= queries.length <= 105queries[i].length == 20 <= li <= ri < nums.lengthThe goal is to reduce the nums array to all zeros using the fewest possible queries. To efficiently adjust multiple ranges in the nums array, we can employ a 'difference array' to record the increment/decrement at particular indices. This allows constant-time updates over a subrange.
Once the necessary decrements for each range are calculated, test different combinations of queries to find the maximal number of query removals that still result in nums becoming all zeros.
This code applies the difference array technique. It processes the queries to adjust the nums array, then tests all subarrays of the query sequences by removing one query at a time. If zero array can be achieved by skipped queries, it outputs the number of skippable queries. The approach is greedy – trying minimal number of changes until zero array is possible.
JavaScript
Time Complexity: O(M * N), where N is the length of nums and M is the number of queries since we attempt each query removal.
Space Complexity: O(N) for the difference array.
This approach involves treating queries in a greedily prioritized manner. Using a priority queue to always select and process a query that maximizes the zero effect over the largest overlapping range just after it processes the overlapping range, thus allowing maximum flexibility in decrements.
The C++ solution employs a min-heap to greedily select the smallest possible range query to remove, ensuring efficiency by always considering the next largest decrement range effectively. This ensures that minimal queries are used to zero the nums array, while making sure a removal is beneficial.
Time Complexity: O(N log N) (due to the heap operations).
Space Complexity: O(N).
| Approach | Complexity |
|---|---|
| Difference Array Technique | Time Complexity: Space Complexity: |
| Greedy with Priority Queue | Time Complexity: Space Complexity: |
Zero Array Transformation II | Brute Force | Better | Leetcode 3356 | codestorywithMIK • codestorywithMIK • 13,445 views views
Watch 9 more video solutions →Practice Zero Array Transformation III with our built-in code editor and test cases.
Practice on FleetCode