Zero Array Transformation II

Med

#2982Time: 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.

Patterns

Prefix Sum

Algorithms

Binary Search

Data structures

Array

Prompt

You are given an integer array nums of length n and a 2D array queries where queries[i] = [l_i, r_i, val_i].

Each queries[i] represents the following action on nums:

Decrement the value at each index in the range [l_i, r_i] in nums by at most val_i.
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].
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 of k is 2.

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].
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.

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 5 * 10⁵
1 <= queries.length <= 10⁵
queries[i].length == 3
0 <= l_i <= r_i < nums.length
1 <= val_i <= 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 k from 1 to m (the total number of queries).
For each k, create an array totalDecrement of size n, initialized to all zeros.
Iterate through the first k queries (from i = 0 to k-1).
For each query [l, r, val], iterate through the range of indices j from l to r and add val to totalDecrement[j].
After processing the k queries, perform a final check. Iterate through all indices j from 0 to n-1.
If totalDecrement[j] < nums[j] for any j, this k is not sufficient, so continue to the next k.
If totalDecrement[j] >= nums[j] for all j, then k is the minimum number of queries required. Return k.
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.

1class Solution {2    public int zeroArray(int[] nums, int[][] queries) {3        int n = nums.length;4        int m = queries.length;5 6        boolean allZero = true;7        for (int num : nums) {8            if (num != 0) {9                allZero = false;10                break;11            }12        }13        if (allZero) return 0;14 15        for (int k = 1; k <= m; k++) {16            long[] totalDecrement = new long[n];17            for (int i = 0; i < k; i++) {18                int l = queries[i][0];19                int r = queries[i][1];20                int val = queries[i][2];21                for (int j = l; j <= r; j++) {22                    totalDecrement[j] += val;23                }24            }25 26            boolean possible = true;27            for (int i = 0; i < n; i++) {28                if (totalDecrement[i] < nums[i]) {29                    possible = false;30                    break;31                }32            }33 34            if (possible) {35                return k;36            }37        }38 39        return -1;40    }41}

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.

A more optimized approach uses binary search on the answer k. The key observation is that the problem has a monotonic property: if the array can be zeroed out with k queries, it can certainly be zeroed out with k+1 queries. This allows us to binary search for the minimum k in the range [1, m].

The main challenge is to efficiently implement the check(k) function, which determines if the first k queries are sufficient. A naive check is too slow. We can optimize this check using a difference array. For a given k, we can compute the total decrement capacity for all indices in O(k+n) time instead of O(k*n).

Algorithm

Observe that if k queries are sufficient, any k' > k queries will also be sufficient. This monotonic property allows binary searching for the answer.
Set up a binary search for k in the range [1, m], where m is the number of queries.
For each mid value of k in the binary search, use a check(k) function to verify if the first k queries are sufficient.
check(k) function using Difference Array: a. Create a difference array diff of size n+1, initialized to zeros. b. For each of the first k queries [l, r, val], update the difference array: diff[l] += val and diff[r+1] -= val. c. Reconstruct the total decrement values. Iterate from j=0 to n-1, maintaining a currentDecrement sum. Update currentDecrement += diff[j]. d. At each index j, check if currentDecrement < nums[j]. If so, k is insufficient, return false. e. If the loop completes, k is sufficient, return true.
Binary Search Logic: a. If check(mid) is true, mid is a potential answer. Try for a smaller k: ans = mid, high = mid - 1. b. If check(mid) is false, mid is too small. Need more queries: low = mid + 1.
Return the final ans found.

Walkthrough

We can binary search for the minimum number of queries k. The search space for k is from 1 to m.

For a given k (let's call it mid in the binary search), we need an efficient check(mid) function. This function must verify that for every index j, the sum of val from all queries i < mid that cover j is at least nums[j].

Calculating this sum for all j involves multiple range additions. This can be done efficiently using a difference array. The check(mid) function works as follows:

Create a difference array diff of size n+1.
For each of the first mid queries [l, r, val], we apply the update: diff[l] += val and diff[r+1] -= val. This takes O(mid) time in total.
After processing all mid queries, we can find the final decrement capacity for each index by computing the prefix sum of the diff array. We can do this and check the condition in a single pass. We iterate from j=0 to n-1, maintaining a running sum currentDecrement. At each index j, we update currentDecrement += diff[j] and then check if currentDecrement < nums[j]. If this inequality holds, mid is not enough, and check(mid) returns false.
If we iterate through all indices without this condition failing, mid is sufficient, and check(mid) returns true.

The binary search proceeds as usual: if check(mid) is true, we try a smaller k; otherwise, we need a larger k.

1class Solution {2    public int zeroArray(int[] nums, int[][] queries) {3        int n = nums.length;4        int m = queries.length;5 6        boolean allZero = true;7        for (int num : nums) {8            if (num != 0) {9                allZero = false;10                break;11            }12        }13        if (allZero) return 0;14 15        int ans = -1;16        int low = 1, high = m;17 18        while (low <= high) {19            int mid = low + (high - low) / 2;20            if (isPossible(nums, queries, mid, n)) {21                ans = mid;22                high = mid - 1;23            } else {24                low = mid + 1;25            }26        }27        return ans;28    }29 30    private boolean isPossible(int[] nums, int[][] queries, int k, int n) {31        long[] diff = new long[n + 1];32 33        for (int i = 0; i < k; i++) {34            int l = queries[i][0];35            int r = queries[i][1];36            int val = queries[i][2];37            diff[l] += val;38            if (r + 1 <= n) {39                diff[r + 1] -= val;40            }41        }42 43        long currentDecrement = 0;44        for (int i = 0; i < n; i++) {45            currentDecrement += diff[i];46            if (currentDecrement < nums[i]) {47                return false;48            }49        }50        return true;51    }52}

Complexity

Time

O((n + m) * log m) - The binary search performs `log m` iterations. In each iteration, the `check` function takes `O(k + n)` time, where `k` is at most `m`. So, the complexity is `O((n+m) * log m)`.

Space

O(n) - for the difference array used within the `check` function.

Trade-offs

Pros

Much more efficient than the brute-force approach.
Guaranteed to pass within the time limits for the given constraints.

Cons

More complex to implement than the brute-force approach.
Can be slightly less performant than the segment tree approach if n and m are large and comparable.

This approach processes the queries iteratively and uses a powerful data structure, a Segment Tree, to keep track of the state of the array. The goal is to find the first query k for which the total decrement capacity at every index j is at least nums[j]. This condition can be rewritten as total_decrement[j] - nums[j] >= 0 for all j. We can maintain the values of total_decrement[j] - nums[j] in a segment tree and, after each query, check if the minimum value in the tree has become non-negative.

Algorithm

Rephrase the condition: for a given set of queries, nums can be zeroed if total_decrement[j] >= nums[j] for all j. This is equivalent to min(total_decrement[j] - nums[j]) >= 0.
Let A[j] = total_decrement[j] - nums[j]. Initially, total_decrement[j] = 0, so A[j] = -nums[j].
Build a Segment Tree on this initial array A. The segment tree must support range additions and querying the global minimum. A segment tree with lazy propagation is suitable.
Iterate through the queries one by one, from i = 0 to m-1.
For each query [l, r, val], it increases the total_decrement by val in the range [l, r]. This corresponds to adding val to A[j] for j in [l, r].
Perform a range update on the segment tree, adding val to the range [l, r]. This takes O(log n) time.
After each update, query the minimum value in the segment tree. This is an O(1) operation as it's stored at the root.
If the minimum value is >= 0, it means the condition is met for all indices. The current query count (i+1) is the minimum k. Return i+1.
If the loop finishes and the condition is never met, return -1.

Walkthrough

The most efficient solution involves simulating the process query by query while using a segment tree with lazy propagation to efficiently update and check the required condition.

The condition we need to satisfy is total_decrement[j] >= nums[j] for all j. Let's define an array A[j] = total_decrement[j] - nums[j]. The condition becomes A[j] >= 0 for all j, or equivalently, min(A) >= 0.

Initially, before any queries are processed, total_decrement[j] = 0, so we can initialize our data structure with A[j] = -nums[j].

We build a segment tree on this initial array A. Each node in the tree will store the minimum value in its corresponding range. We also need lazy propagation to handle range updates efficiently.

We then iterate through the queries from i = 0 to m-1. For each query [l, r, val], we need to add val to A[j] for all j in the range [l, r]. This is a range addition update, which can be done in O(log n) time on the segment tree.

After each update, we check the minimum value of the entire array A. This value is stored at the root of our segment tree, so the check is an O(1) operation. If this minimum value is greater than or equal to 0, we have found the smallest number of queries needed. We return the current query count, which is i + 1.

If we iterate through all m queries and the minimum value never becomes non-negative, it's impossible to zero out the array, so we return -1.

1class Solution {2    long[] tree;3    long[] lazy;4    int n;5 6    private void push(int node, int start, int end) {7        if (lazy[node] == 0) return;8        tree[node] += lazy[node];9        if (start != end) {10            lazy[2 * node] += lazy[node];11            lazy[2 * node + 1] += lazy[node];12        }13        lazy[node] = 0;14    }15 16    private void build(long[] arr, int node, int start, int end) {17        if (start == end) {18            tree[node] = arr[start];19            return;20        }21        int mid = start + (end - start) / 2;22        build(arr, 2 * node, start, mid);23        build(arr, 2 * node + 1, mid + 1, end);24        tree[node] = Math.min(tree[2 * node], tree[2 * node + 1]);25    }26 27    private void update(int node, int start, int end, int l, int r, int val) {28        push(node, start, end);29        if (start > r || end < l) return;30        if (l <= start && end <= r) {31            lazy[node] += val;32            push(node, start, end);33            return;34        }35        int mid = start + (end - start) / 2;36        update(2 * node, start, mid, l, r, val);37        update(2 * node + 1, mid + 1, end, l, r, val);38        push(2 * node, start, mid);39        push(2 * node + 1, mid + 1, end);40        tree[node] = Math.min(tree[2 * node], tree[2 * node + 1]);41    }42 43    public int zeroArray(int[] nums, int[][] queries) {44        this.n = nums.length;45        long[] initialArr = new long[n];46        boolean allZero = true;47        for (int i = 0; i < n; i++) {48            initialArr[i] = -nums[i];49            if (nums[i] != 0) allZero = false;50        }51        if (allZero) return 0;52 53        tree = new long[4 * n];54        lazy = new long[4 * n];55        build(initialArr, 1, 0, n - 1);56 57        for (int i = 0; i < queries.length; i++) {58            int l = queries[i][0];59            int r = queries[i][1];60            int val = queries[i][2];61            update(1, 0, n - 1, l, r, val);62            if (tree[1] >= 0) {63                return i + 1;64            }65        }66 67        return -1;68    }69}

Complexity

Time

O(n + m * log n) - It takes `O(n)` to build the segment tree initially. Then, for each of the `m` queries, we perform a range update which takes `O(log n)` time.

Space

O(n) - for the segment tree and the lazy propagation array, both of which are proportional to `n`.

Trade-offs

Pros

The most efficient approach for the given constraints.
Processes queries sequentially, which can be more intuitive than binary search.

Cons

Implementation is complex, requiring a correctly implemented segment tree with lazy propagation.

Solutions

Solution

1class Solution {2private3  int n;4private5  int[] nums;6private7  int[][] queries;8public9  int minZeroArray(int[] nums, int[][] queries) {10    this.nums = nums;11    this.queries = queries;12    n = nums.length;13    int m = queries.length;14    int l = 0, r = m + 1;15    while (l < r) {16      int mid = (l + r) >> 1;17      if (check(mid)) {18        r = mid;19      } else {20        l = mid + 1;21      }22    }23    return l > m ? -1 : l;24  }25private26  boolean check(int k) {27    int[] d = new int[n + 1];28    for (int i = 0; i < k; ++i) {29      int l = queries[i][0], r = queries[i][1], val = queries[i][2];30      d[l] += val;31      d[r + 1] -= val;32    }33    for (int i = 0, s = 0; i < n; ++i) {34      s += d[i];35      if (nums[i] > s) {36        return false;37      }38    }39    return true;40  }41}

1class Solution {2public:3  int minZeroArray(vector<int> &nums, vector<vector<int>> &queries) {4    int n = nums.size();5    int d[n + 1];6    int m = queries.size();7    int l = 0, r = m + 1;8    auto check = [&](int k) -> bool {9      memset(d, 0, sizeof(d));10      for (int i = 0; i < k; ++i) {11        int l = queries[i][0], r = queries[i][1], val = queries[i][2];12        d[l] += val;13        d[r + 1] -= val;14      }15      for (int i = 0, s = 0; i < n; ++i) {16        s += d[i];17        if (nums[i] > s) {18          return false;19        }20      }21      return true;22    };23    while (l < r) {24      int mid = (l + r) >> 1;25      if (check(mid)) {26        r = mid;27      } else {28        l = mid + 1;29      }30    }31    return l > m ? -1 : l;32  }33};

1class Solution:2    def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int: def check(k: int) -> bool: d = [0] * (len(nums) + 1) for l, r, val in queries[: k]: d[l] += val d[r + 1] -= val s = 0 for x, y in zip(nums, d): s += y if x > s: return False return True m = len(queries) l = bisect_left(range(m + 1), True, key=check) return - 1 if l > m else l

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.

← Previous

Previous problem

Next problem

Solution

1class Solution {2private3  int n;4private5  int[] nums;6private7  int[][] queries;8public9  int minZeroArray(int[] nums, int[][] queries) {10    this.nums = nums;11    this.queries = queries;12    n = nums.length;13    int m = queries.length;14    int l = 0, r = m + 1;15    while (l < r) {16      int mid = (l + r) >> 1;17      if (check(mid)) {18        r = mid;19      } else {20        l = mid + 1;21      }22    }23    return l > m ? -1 : l;24  }25private26  boolean check(int k) {27    int[] d = new int[n + 1];28    for (int i = 0; i < k; ++i) {29      int l = queries[i][0], r = queries[i][1], val = queries[i][2];30      d[l] += val;31      d[r + 1] -= val;32    }33    for (int i = 0, s = 0; i < n; ++i) {34      s += d[i];35      if (nums[i] > s) {36        return false;37      }38    }39    return true;40  }41}

1class Solution {2public:3  int minZeroArray(vector<int> &nums, vector<vector<int>> &queries) {4    int n = nums.size();5    int d[n + 1];6    int m = queries.size();7    int l = 0, r = m + 1;8    auto check = [&](int k) -> bool {9      memset(d, 0, sizeof(d));10      for (int i = 0; i < k; ++i) {11        int l = queries[i][0], r = queries[i][1], val = queries[i][2];12        d[l] += val;13        d[r + 1] -= val;14      }15      for (int i = 0, s = 0; i < n; ++i) {16        s += d[i];17        if (nums[i] > s) {18          return false;19        }20      }21      return true;22    };23    while (l < r) {24      int mid = (l + r) >> 1;25      if (check(mid)) {26        r = mid;27      } else {28        l = mid + 1;29      }30    }31    return l > m ? -1 : l;32  }33};

1class Solution:2    def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int: def check(k: int) -> bool: d = [0] * (len(nums) + 1) for l, r, val in queries[: k]: d[l] += val d[r + 1] -= val s = 0 for x, y in zip(nums, d): s += y if x > s: return False return True m = len(queries) l = bisect_left(range(m + 1), True, key=check) return - 1 if l > m else l

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.