Watch 10 video solutions for Zero Array Transformation II, a medium level problem involving Array, Binary Search, Prefix Sum. This walkthrough by codestorywithMIK has 13,445 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 5