Zero Array Transformation II
MedPrompt
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:
- Decrement the value at each index in the range
[li, ri]innumsby at mostvali. - The amount by which each value is decremented can be chosen independently for each index.
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:
- For i = 0 (l = 0, r = 2, val = 1):
- Decrement values at indices
[0, 1, 2]by[1, 0, 1]respectively. - The array will become
[1, 0, 1].
- Decrement values at indices
- For i = 1 (l = 0, r = 2, val = 1):
- Decrement values at indices
[0, 1, 2]by[1, 0, 1]respectively. - The array will become
[0, 0, 0], which is a Zero Array. Therefore, the minimum value ofkis 2.
- Decrement values at indices
Example 2:
Input: nums = [4,3,2,1], queries = [[1,3,2],[0,2,1]]
Output: -1
Explanation:
- For i = 0 (l = 1, r = 3, val = 2):
- Decrement values at indices
[1, 2, 3]by[2, 2, 1]respectively. - The array will become
[4, 1, 0, 0].
- Decrement values at indices
- For i = 1 (l = 0, r = 2, val = 1):
- Decrement values at indices
[0, 1, 2]by[1, 1, 0]respectively. - The array will become
[3, 0, 0, 0], which is not a Zero Array.
- Decrement values at indices
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 5 * 1051 <= queries.length <= 105queries[i].length == 30 <= li <= ri < nums.length1 <= vali <= 5
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly simulates the problem statement by checking each possible value of k sequentially. It starts from k=1 and goes up to m (the total number of queries). For each k, it calculates the total possible decrement for every element in nums by summing up the val from the first k queries that cover each index. If the total decrement for every element is sufficient to make it zero, then that k is the minimum, and we return it.
Algorithm
- Iterate
kfrom 1 tom(the total number of queries). - For each
k, create an arraytotalDecrementof sizen, initialized to all zeros. - Iterate through the first
kqueries (fromi = 0tok-1). - For each query
[l, r, val], iterate through the range of indicesjfromltorand addvaltototalDecrement[j]. - After processing the
kqueries, perform a final check. Iterate through all indicesjfrom0ton-1. - If
totalDecrement[j] < nums[j]for anyj, thiskis not sufficient, so continue to the nextk. - If
totalDecrement[j] >= nums[j]for allj, thenkis the minimum number of queries required. Returnk. - If the loop completes without finding a suitable
k, it's impossible to make the array a zero array. Return -1.
Walkthrough
The brute-force method involves a straightforward check for every possible answer k. We loop k from 1 to m. In each iteration, we determine if the first k queries are enough to transform nums into a zero array.
To do this check for a given k, we can use an auxiliary array, say totalDecrement, of the same size as nums and initialized to zeros. We then iterate through the first k queries. For each query [l, r, val], we add val to every element of totalDecrement from index l to r. This simulates the accumulation of decrement capacity.
After processing all k queries, totalDecrement[j] will hold the maximum possible amount by which nums[j] can be decremented. We then iterate through nums and totalDecrement simultaneously. If we find any index j where totalDecrement[j] < nums[j], it means we cannot make nums[j] zero, so this k is not sufficient. If totalDecrement[j] >= nums[j] for all indices j, we have found our minimum k and can return it immediately. If the outer loop finishes, no such k exists, and we return -1.
class Solution { public int zeroArray(int[] nums, int[][] queries) { int n = nums.length; int m = queries.length; boolean allZero = true; for (int num : nums) { if (num != 0) { allZero = false; break; } } if (allZero) return 0; for (int k = 1; k <= m; k++) { long[] totalDecrement = new long[n]; for (int i = 0; i < k; i++) { int l = queries[i][0]; int r = queries[i][1]; int val = queries[i][2]; for (int j = l; j <= r; j++) { totalDecrement[j] += val; } } boolean possible = true; for (int i = 0; i < n; i++) { if (totalDecrement[i] < nums[i]) { possible = false; break; } } if (possible) { return k; } } return -1; }}Complexity
Time
O(m² * n) - In the worst case, we iterate `k` from 1 to `m`. For each `k`, we iterate through `k` queries, and for each query, we might iterate up to `n` elements. This leads to a complexity of roughly Σ(k=1 to m) k*n, which is O(m² * n).
Space
O(n) - to store the `totalDecrement` array.
Trade-offs
Pros
Simple to understand and implement.
Cons
Extremely inefficient due to nested loops.
Will result in a 'Time Limit Exceeded' error for the given constraints.
Solutions
Solution
class Solution {private int n;private int[] nums;private int[][] queries;public int minZeroArray(int[] nums, int[][] queries) { this.nums = nums; this.queries = queries; n = nums.length; int m = queries.length; int l = 0, r = m + 1; while (l < r) { int mid = (l + r) >> 1; if (check(mid)) { r = mid; } else { l = mid + 1; } } return l > m ? -1 : l; }private boolean check(int k) { int[] d = new int[n + 1]; for (int i = 0; i < k; ++i) { int l = queries[i][0], r = queries[i][1], val = queries[i][2]; d[l] += val; d[r + 1] -= val; } for (int i = 0, s = 0; i < n; ++i) { s += d[i]; if (nums[i] > s) { return false; } } return true; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.