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 <= 5In 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
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.
| 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. |
Zero Array Transformation II | Brute Force | Better | Leetcode 3356 | codestorywithMIK • codestorywithMIK • 13,445 views views
Watch 9 more video solutions →Practice Zero Array Transformation II with our built-in code editor and test cases.
Practice on FleetCode