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 <= 5class Solution {
public int minZeroArray(int[] nums, int[][] queries) {
int n = nums.length, sum = 0, k = 0;
int[] differenceArray = new int[n + 1];
// Iterate through nums
for (int index = 0; index < n; index++) {
// Iterate through queries while current index of nums cannot equal zero
while (sum + differenceArray[index] < nums[index]) {
k++;
// Zero array isn't formed after all queries are processed
if (k > queries.length) {
return -1;
}
int left = queries[k - 1][0], right = queries[k - 1][1], val =
queries[k - 1][2];
// Process start and end of range
if (right >= index) {
differenceArray[Math.max(left, index)] += val;
differenceArray[right + 1] -= val;
}
}
// Update prefix sum at current index
sum += differenceArray[index];
}
return k;
}
}