You are given an integer array nums of length n and a 2D array queries where queries[i] = [li, ri, vali].
Each queries[i] represents the following action on nums:
[li, ri] in nums by at most vali.A Zero Array is an array with all its elements equal to 0.
Return the minimum possible non-negative value of k, such that after processing the first k queries in sequence, nums becomes a Zero Array. If no such k exists, return -1.
Example 1:
Input: nums = [2,0,2], queries = [[0,2,1],[0,2,1],[1,1,3]]
Output: 2
Explanation:
[0, 1, 2] by [1, 0, 1] respectively.[1, 0, 1].[0, 1, 2] by [1, 0, 1] respectively.[0, 0, 0], which is a Zero Array. Therefore, the minimum value of k is 2.Example 2:
Input: nums = [4,3,2,1], queries = [[1,3,2],[0,2,1]]
Output: -1
Explanation:
[1, 2, 3] by [2, 2, 1] respectively.[4, 1, 0, 0].[0, 1, 2] by [1, 1, 0] respectively.[3, 0, 0, 0], which is not a Zero Array.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 5 * 1051 <= queries.length <= 105queries[i].length == 30 <= li <= ri < nums.length1 <= vali <= 5Problem Overview: You are given an integer array nums and a list of range queries. Each query allows decreasing every element in a subarray by a certain value. The task is to determine the minimum number of queries (in order) required so that every element in nums becomes zero or negative. If it is impossible even after all queries, return -1.
Approach 1: Brute Force Simulation (O(n * m) time, O(1) space)
The direct approach applies queries one by one and updates the affected range in the array. For each query [l, r, val], iterate from l to r and subtract val from each element. After applying a query, scan the array to check if all values are <= 0. If so, return the number of queries used so far. This approach clearly shows the mechanics of the problem but becomes slow when both the array length and number of queries are large because every query touches up to n elements.
Approach 2: Binary Search + Difference Array (O((n + m) log m) time, O(n) space)
The key observation is that queries are applied in order, and we only care about the earliest prefix of queries that can reduce every index enough. This makes the problem monotonic: if the first k queries can zero the array, any k+1 queries will also work. That property allows binary search over the number of queries.
To efficiently evaluate whether the first k queries are sufficient, use a difference array for range updates. For each query [l, r, val], add val at diff[l] and subtract it at diff[r+1]. After processing the first k queries, compute the prefix sum to obtain the total decrement available for each index. If the accumulated decrement at index i is at least nums[i], that element can be reduced to zero. Otherwise, the first k queries are insufficient.
This technique converts repeated range updates into O(1) operations and a single prefix sum sweep. It leverages ideas from prefix sums and efficient range updates commonly used in array problems.
Recommended for interviews: The binary search + difference array approach is the expected solution. The brute force simulation demonstrates understanding of the operations, but it does not scale. Interviewers typically look for recognition of the monotonic condition and the use of a difference array to process range updates efficiently.
In this approach, we will iterate through each query and update the array accordingly by decrementing each value in the specified range by the given value in the query. This method directly simulates applying each query to the array.
The C solution iteratively applies each query to the nums array. For each query, it updates the values in the range [l, r] by decrementing them by val, ensuring no negative values occur. After each query application, nums is checked to see if it is entirely zeros, at which point the index of the current query (incremented by one for a 1-based position) is returned as the result. If no such condition is met by the end of all queries, it returns -1.
Time Complexity: O(n * m), where n is the length of nums and m is the number of queries. Each query may require iterating over the entire range of the array.
Space Complexity: O(1), since all modifications are done in place.
This approach utilizes a difference array to optimize range updates. Instead of manually applying the decrement to each element between l and r, we will maintain a difference array where each query updates only the boundary indices. After processing all queries, the difference array is used to decrement the original array and check for the Zero Array condition efficiently.
The C solution uses a difference array to efficiently handle range decrements. Instead of decrementing each element directly, it adjusts the boundaries using the difference array and then applies the accumulated changes across nums to verify if it becomes a Zero Array. This integration of differential logic reduces the operational size for each query application.
Time Complexity: O(n + m), where n is the length of nums and m is the number of queries, optimizing the brute-force complexity significantly.
Space Complexity: O(n), for the difference array storage.
We notice that the more queries we use, the easier it is to turn the array into a zero array, which shows monotonicity. Therefore, we can use binary search to enumerate the number of queries and check whether the array can be turned into a zero array after the first k queries.
We define the left boundary l and right boundary r for binary search, initially l = 0, r = m + 1, where m is the number of queries. We define a function check(k) to indicate whether the array can be turned into a zero array after the first k queries. We can use a difference array to maintain the value of each element.
Define an array d of length n + 1, initialized to all 0. For each of the first k queries [l, r, val], we add val to d[l] and subtract val from d[r + 1].
Then we iterate through the array d in the range [0, n - 1], accumulating the prefix sum s. If nums[i] > s, it means nums cannot be transformed into a zero array, so we return false.
During the binary search, if check(k) returns true, it means the array can be turned into a zero array, so we update the right boundary r to k; otherwise, we update the left boundary l to k + 1.
Finally, we check whether l > m. If so, return -1; otherwise, return l.
The time complexity is O((n + m) times log m), and the space complexity is O(n), where n and m are the lengths of the array nums and queries, respectively.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n * m), where n is the length of nums and m is the number of queries. Each query may require iterating over the entire range of the array. |
| Difference Array Approach for Range Update | Time Complexity: O(n + m), where n is the length of nums and m is the number of queries, optimizing the brute-force complexity significantly. |
| Difference Array + Binary Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n * m) | O(1) | Useful for understanding the mechanics of the queries or when constraints are very small. |
| Binary Search + Difference Array | O((n + m) log m) | O(n) | Optimal solution for large inputs where many range updates must be processed efficiently. |
Zero Array Transformation II | Brute Force | Better | Leetcode 3356 | codestorywithMIK • codestorywithMIK • 20,566 views views
Watch 9 more video solutions →Practice Zero Array Transformation II with our built-in code editor and test cases.
Practice on FleetCode