# Zero Array Transformation II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/zero-array-transformation-ii)
Canonical: https://scaleengineer.com/dsa/problems/zero-array-transformation-ii
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
---
## Problem
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]` in `nums` by **at most** `vali`.
* 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 <= 105`
* `0 <= nums[i] <= 5 * 105`
* `1 <= queries.length <= 105`
* `queries[i].length == 3`
* `0 <= li <= ri < nums.length`
* `1 <= vali <= 5`

# Approaches
## Brute-Force Simulation
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
1. Iterate `k` from 1 to `m` (the total number of queries).
2. For each `k`, create an array `totalDecrement` of size `n`, initialized to all zeros.
3. Iterate through the first `k` queries (from `i = 0` to `k-1`).
4. For each query `[l, r, val]`, iterate through the range of indices `j` from `l` to `r` and add `val` to `totalDecrement[j]`.
5. After processing the `k` queries, perform a final check. Iterate through all indices `j` from `0` to `n-1`.
6. If `totalDecrement[j] < nums[j]` for any `j`, this `k` is not sufficient, so continue to the next `k`.
7. If `totalDecrement[j] >= nums[j]` for all `j`, then `k` is the minimum number of queries required. Return `k`.
8. If the loop completes without finding a suitable `k`, it's impossible to make the array a zero array. Return -1.

## Binary Search on Answer with Difference Array
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)`.
**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.
**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.
### Explanation
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:
1. Create a difference array `diff` of size `n+1`.
2. 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.
3. 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`.
4. 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`.

```java
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;

        int ans = -1;
        int low = 1, high = m;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (isPossible(nums, queries, mid, n)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    private boolean isPossible(int[] nums, int[][] queries, int k, int n) {
        long[] diff = new long[n + 1];

        for (int i = 0; i < k; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            int val = queries[i][2];
            diff[l] += val;
            if (r + 1 <= n) {
                diff[r + 1] -= val;
            }
        }

        long currentDecrement = 0;
        for (int i = 0; i < n; i++) {
            currentDecrement += diff[i];
            if (currentDecrement < nums[i]) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
1. Observe that if `k` queries are sufficient, any `k' > k` queries will also be sufficient. This monotonic property allows binary searching for the answer.
2. Set up a binary search for `k` in the range `[1, m]`, where `m` is the number of queries.
3. For each `mid` value of `k` in the binary search, use a `check(k)` function to verify if the first `k` queries are sufficient.
4. **`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`.
5. **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`.
6. Return the final `ans` found.

## Iterative Simulation with Segment Tree
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.
**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`.
**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.
### Explanation
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.

```java
class Solution {
    long[] tree;
    long[] lazy;
    int n;

    private void push(int node, int start, int end) {
        if (lazy[node] == 0) return;
        tree[node] += lazy[node];
        if (start != end) {
            lazy[2 * node] += lazy[node];
            lazy[2 * node + 1] += lazy[node];
        }
        lazy[node] = 0;
    }

    private void build(long[] arr, int node, int start, int end) {
        if (start == end) {
            tree[node] = arr[start];
            return;
        }
        int mid = start + (end - start) / 2;
        build(arr, 2 * node, start, mid);
        build(arr, 2 * node + 1, mid + 1, end);
        tree[node] = Math.min(tree[2 * node], tree[2 * node + 1]);
    }

    private void update(int node, int start, int end, int l, int r, int val) {
        push(node, start, end);
        if (start > r || end < l) return;
        if (l <= start && end <= r) {
            lazy[node] += val;
            push(node, start, end);
            return;
        }
        int mid = start + (end - start) / 2;
        update(2 * node, start, mid, l, r, val);
        update(2 * node + 1, mid + 1, end, l, r, val);
        push(2 * node, start, mid);
        push(2 * node + 1, mid + 1, end);
        tree[node] = Math.min(tree[2 * node], tree[2 * node + 1]);
    }

    public int zeroArray(int[] nums, int[][] queries) {
        this.n = nums.length;
        long[] initialArr = new long[n];
        boolean allZero = true;
        for (int i = 0; i < n; i++) {
            initialArr[i] = -nums[i];
            if (nums[i] != 0) allZero = false;
        }
        if (allZero) return 0;

        tree = new long[4 * n];
        lazy = new long[4 * n];
        build(initialArr, 1, 0, n - 1);

        for (int i = 0; i < queries.length; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            int val = queries[i][2];
            update(1, 0, n - 1, l, r, val);
            if (tree[1] >= 0) {
                return i + 1;
            }
        }

        return -1;
    }
}
```
### Algorithm
1. 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`.
2. Let `A[j] = total_decrement[j] - nums[j]`. Initially, `total_decrement[j] = 0`, so `A[j] = -nums[j]`.
3. 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.
4. Iterate through the queries one by one, from `i = 0` to `m-1`.
5. 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]`.
6. Perform a range update on the segment tree, adding `val` to the range `[l, r]`. This takes `O(log n)` time.
7. After each update, query the minimum value in the segment tree. This is an `O(1)` operation as it's stored at the root.
8. 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`.
9. If the loop finishes and the condition is never met, return -1.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minZeroArray(vector<int> &nums, vector<vector<int>> &queries) {
    int n = nums.size();
    int d[n + 1];
    int m = queries.size();
    int l = 0, r = m + 1;
    auto check = [&](int k) -> bool {
      memset(d, 0, sizeof(d));
      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;
    };
    while (l < r) {
      int mid = (l + r) >> 1;
      if (check(mid)) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l > m ? -1 : l;
  }
};

```

### Python

```python
class Solution:
    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

```