# Zero Array Transformation IV
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/zero-array-transformation-iv)
Canonical: https://scaleengineer.com/dsa/problems/zero-array-transformation-iv
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**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`:

* Select a subset of indices in the range `[li, ri]` from `nums`.
* Decrement the value at each selected index by **exactly** `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:**

* **For query 0 (l = 0, r = 2, val = 1):**  
  * Decrement the values at indices `[0, 2]` by 1.
  * The array will become `[1, 0, 1]`.
* **For query 1 (l = 0, r = 2, val = 1):**  
  * Decrement the values at indices `[0, 2]` by 1.
  * 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:**

It is impossible to make nums a Zero Array even after all the queries.

**Example 3:**

**Input:** nums = \[1,2,3,2,1\], queries = \[\[0,1,1\],\[1,2,1\],\[2,3,2\],\[3,4,1\],\[4,4,1\]\]

**Output:** 4

**Explanation:**

* **For query 0 (l = 0, r = 1, val = 1):**  
  * Decrement the values at indices `[0, 1]` by `1`.
  * The array will become `[0, 1, 3, 2, 1]`.
* **For query 1 (l = 1, r = 2, val = 1):**  
  * Decrement the values at indices `[1, 2]` by 1.
  * The array will become `[0, 0, 2, 2, 1]`.
* **For query 2 (l = 2, r = 3, val = 2):**  
  * Decrement the values at indices `[2, 3]` by 2.
  * The array will become `[0, 0, 0, 0, 1]`.
* **For query 3 (l = 3, r = 4, val = 1):**  
  * Decrement the value at index 4 by 1.
  * The array will become `[0, 0, 0, 0, 0]`. Therefore, the minimum value of `k` is 4.

**Example 4:**

**Input:** nums = \[1,2,3,2,6\], queries = \[\[0,1,1\],\[0,2,1\],\[1,4,2\],\[4,4,4\],\[3,4,1\],\[4,4,5\]\]

**Output:** 4

**Constraints:**

* `1 <= nums.length <= 10`
* `0 <= nums[i] <= 1000`
* `1 <= queries.length <= 1000`
* `queries[i] = [li, ri, vali]`
* `0 <= li <= ri < nums.length`
* `1 <= vali <= 10`

# Approaches
## Brute Force with Backtracking
This approach simulates the process for every possible number of queries `k`, from 1 up to the total number of queries. For each `k`, it checks if it's possible to make the array `nums` all zeros. This check is done by solving a subset sum problem for each element `nums[j]`. The subset sum problem itself is solved using a brute-force backtracking (or recursive) method, which explores all possibilities.
**Time:** O(n * Q * 2^Q), where n is the length of `nums` and Q is the number of queries. For each `k` up to `Q`, we check `n` indices. The check for each index involves solving a subset sum problem on a set of up to `k` values, which takes O(2^k) time with backtracking. The total time is dominated by the largest `k`. · **Space:** O(Q), where Q is the number of queries. This space is used for the recursion stack depth during the backtracking process and to store the list of applicable query values for an index.
**Pros:** Conceptually simple and easy to understand.; Directly translates the problem statement into code.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' error for all but the smallest inputs.
### Explanation
The core idea is to test each potential answer `k` sequentially. For a given `k`, we must determine if there's a way to apply the first `k` queries to make every `nums[j]` zero. This decomposes into `n` independent subset sum problems. For each `nums[j]`, we need to find if it can be expressed as a sum of some of the `val_i` from the first `k` queries that cover index `j`.

The backtracking function `canFormSum` explores all subsets of the applicable query values to see if any sum up to the target `nums[j]`. It does this by making two recursive calls at each step: one where the current value is included in the sum, and one where it's excluded.

```java
class Solution {
    public int zeroArray(int[] nums, int[][] queries) {
        for (int k = 1; k <= queries.length; k++) {
            if (canMakeZero(nums, queries, k)) {
                return k;
            }
        }
        return -1;
    }

    private boolean canMakeZero(int[] nums, int[][] queries, int k) {
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] == 0) continue;
            java.util.List<Integer> options = new java.util.ArrayList<>();
            for (int i = 0; i < k; i++) {
                if (queries[i][0] <= j && j <= queries[i][1]) {
                    options.add(queries[i][2]);
                }
            }
            if (!canFormSum(nums[j], options, 0)) {
                return false;
            }
        }
        return true;
    }

    private boolean canFormSum(int target, java.util.List<Integer> options, int index) {
        if (target == 0) return true;
        if (target < 0 || index == options.size()) return false;
        
        // Exclude current option
        if (canFormSum(target, options, index + 1)) {
            return true;
        }
        // Include current option
        if (canFormSum(target - options.get(index), options, index + 1)) {
            return true;
        }
        return false;
    }
}
```
### Algorithm
- For each possible number of queries `k` from 1 to `queries.length`:
  - Call a function `canMakeZero(k)` to check if `nums` can be turned into a zero array.
  - If `canMakeZero(k)` returns `true`, then `k` is the minimum number of queries, so return `k`.
- If the loop completes without finding a solution, return -1.
- The `canMakeZero(k)` function checks each index `j` of `nums`:
  - It gathers all `val_i` from the first `k` queries that are applicable to index `j`.
  - It uses a recursive backtracking function to check if `nums[j]` can be formed by a sum of a subset of these values.
  - If any index `j` fails this check, `canMakeZero(k)` returns `false`.
  - If all indices pass, it returns `true`.

## Binary Search with Dynamic Programming
This approach improves upon the brute-force method by using binary search to find the minimum `k`. The key observation is that the problem is monotonic. The check function, `canMakeZero(k)`, which determines if a solution exists for a given `k`, is implemented efficiently using dynamic programming to solve the underlying subset sum problems.
**Time:** O(log(Q) * n * Q * max(nums)). The binary search performs `O(log Q)` iterations. In each iteration, `canMakeZero` is called. This function iterates through `n` indices, and for each, it iterates through `k` (up to `Q`) queries and updates a DP table of size `max(nums)`. This gives a complexity of `O(n * k * max(nums))` for the check. · **Space:** O(max(nums)), where `max(nums)` is the maximum value in the `nums` array. This space is required for the DP table within the `canMakeZero` function. The DP table is recreated for each index check.
**Pros:** Significantly more efficient than the brute-force approach.; Reduces the search space for `k` from linear to logarithmic.
**Cons:** More complex to implement than a simple iterative approach.; The time complexity, while polynomial, can still be high if `max(nums)` or `queries.length` are large.
### Explanation
Instead of a linear scan for `k`, we can significantly speed up the search by using binary search. The search space for `k` is from 0 to `queries.length`.

For a given `k` (let's say `mid` in the binary search), the `canMakeZero(k)` function determines feasibility. For each index `j`, we need to check if `nums[j]` can be formed by summing a subset of values from the first `k` queries that apply to `j`. This is a classic subset sum problem, which we solve with dynamic programming to avoid the exponential complexity of backtracking.

We create a boolean DP array `dp` of size `nums[j] + 1`. `dp[s]` is true if a total decrement of `s` is possible. We initialize `dp[0] = true`. Then, for each applicable query value `v`, we update the `dp` table: `dp[s] = dp[s] || dp[s - v]` for `s` from `nums[j]` down to `v`. If `dp[nums[j]]` is false after considering all applicable queries, then `k` is not sufficient.

```java
class Solution {
    public int zeroArray(int[] nums, int[][] queries) {
        int low = 0, high = queries.length;
        int ans = -1;

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

    private boolean canMakeZero(int[] nums, int[][] queries, int k) {
        if (k == 0) {
            for (int num : nums) {
                if (num != 0) return false;
            }
            return true;
        }
        
        for (int j = 0; j < nums.length; j++) {
            if (nums[j] == 0) continue;
            
            boolean[] dp = new boolean[nums[j] + 1];
            dp[0] = true;

            for (int i = 0; i < k; i++) {
                if (queries[i][0] <= j && j <= queries[i][1]) {
                    int val = queries[i][2];
                    for (int s = nums[j]; s >= val; s--) {
                        dp[s] = dp[s] || dp[s - val];
                    }
                }
            }
            if (!dp[nums[j]]) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- The problem has a monotonic property: if the array can be zeroed with `k` queries, it can also be zeroed with `k+1` queries. This allows for binary search on the answer `k`.
- Binary search for `k` in the range `[0, queries.length]`.
- For each `mid` value in the binary search, call a helper function `canMakeZero(mid)`.
- The `canMakeZero(k)` function checks if it's possible to zero the array using the first `k` queries.
  - For each index `j`, it solves the subset sum problem for the target `nums[j]` using values from the first `k` applicable queries.
  - This subset sum problem is solved efficiently using dynamic programming.
  - A boolean array `dp` of size `nums[j] + 1` is used, where `dp[s]` is true if sum `s` is achievable.
- If `canMakeZero(mid)` is true, we might find a better answer with fewer queries, so we search in the lower half (`high = mid - 1`). Otherwise, we need more queries and search in the upper half (`low = mid + 1`).

## Iterative Dynamic Programming
This is the most efficient approach. Instead of binary searching for `k`, we process the queries one by one in their given order. We maintain a dynamic programming state that tracks all possible total decrements for each index `j`. After processing each query, we update this state and check if it's now possible to make the entire array zero. The first time this condition is met gives us the minimum `k`.
**Time:** O(Q * n * max(nums)). We iterate through `Q` queries. For each query, we iterate through at most `n` indices. For each of those indices, we perform an update that takes `O(max(nums))` time. The check after each query takes an additional `O(n)` time, which is dominated. · **Space:** O(n * max(nums)). This space is used to store the main DP table `possible`. Given the constraints `n <= 10` and `max(nums) <= 1000`, this is `10 * 1001`, which is feasible.
**Pros:** Most efficient time complexity for the given constraints.; Conceptually straightforward, as it builds the solution incrementally.; Avoids the overhead of binary search.
**Cons:** Requires significant memory for the DP table, which could be an issue if `n` or `max(nums)` were much larger.
### Explanation
This approach builds the solution incrementally. We maintain a DP table, `possible[j][s]`, which tells us if a sum `s` can be formed for index `j` using the queries processed so far. We iterate through the queries one by one. For each query, we update the `possible` sums for all indices it affects. After each query `i` is processed, we check if it's now possible to zero out the entire array. This is done by checking if for every index `j`, `possible[j][nums[j]]` is true. If this condition holds, we have found our answer, and it must be the minimum `k` because we are processing queries in order. The minimum number of queries is therefore `i + 1`.

This method avoids the overhead of binary search and re-computation within the check function, leading to a more direct and often faster solution.

```java
class Solution {
    public int zeroArray(int[] nums, int[][] queries) {
        int n = nums.length;
        int maxVal = 0;
        for (int num : nums) {
            maxVal = Math.max(maxVal, num);
        }

        if (maxVal == 0) {
            return 0;
        }

        boolean[][] possible = new boolean[n][maxVal + 1];
        for (int j = 0; j < n; j++) {
            possible[j][0] = true;
        }

        for (int i = 0; i < queries.length; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            int val = queries[i][2];

            for (int j = l; j <= r; j++) {
                for (int s = maxVal; s >= val; s--) {
                    possible[j][s] = possible[j][s] || possible[j][s - val];
                }
            }

            boolean allZeroable = true;
            for (int j = 0; j < n; j++) {
                if (!possible[j][nums[j]]) {
                    allZeroable = false;
                    break;
                }
            }

            if (allZeroable) {
                return i + 1;
            }
        }

        return -1;
    }
}
```
### Algorithm
- Initialize a 2D boolean DP table `possible[n][max_val + 1]`, where `max_val` is the maximum value in `nums`.
- `possible[j][s]` will store whether a total decrement of `s` is achievable for index `j`.
- For each index `j`, initialize `possible[j][0] = true`.
- Iterate through the queries from `i = 0` to `queries.length - 1`.
  - For the current query `[l, r, val]`, update the `possible` table for all affected indices `j` from `l` to `r`.
  - The update rule is: `possible[j][s] = possible[j][s] || possible[j][s - val]` for `s` from `max_val` down to `val`.
- After processing each query `i`, check if a solution has been found:
  - Assume a solution is possible (`all_zeroable = true`).
  - For each index `j`, check if `possible[j][nums[j]]` is true. If not, set `all_zeroable = false` and break.
  - If `all_zeroable` is still true, we have found the minimum `k`. Return `i + 1`.
- If the loop finishes, no solution was found. Return -1.