# [LeetCode] 3356. Zero Array Transformation II

## Problem

[https://leetcode.com/problems/zero-array-transformation-ii/description](https://leetcode.com/problems/zero-array-transformation-ii/description/?envType=daily-question&envId=2025-03-13)

**Leetcode** - Zero Array Transformation

**Type** - Binary Search, Parametric Search, Line Sweeping

**Difficulty** - Medium

## **Approach & Solution**

We can solve it with binary search and line sweeping. In common, two approach uses diff array to accumulate changes. If diff\[i\] = 3, actual data for num\[i\] is num\[i\] - 3. Given `l, r, val` in `queries`, update `diff` like:

* `diff[l] += val`
    
* `diff[r+1] += val`
    

Binary Search: starting from `lo = 0, hi = k`. If `k(mid)` is available to set 0-array, reduce right side and try the number with less than `k` to minimize the answer, otherwise, reduce left side and try to larger `k`.

Line Sweeping: set pointer k to track the amount of used queries. slide k to right while current nums\[i\] is positive.

\*\* data structure and variables\*\*:

* `diff`: diff\[i\] stores how much subtracted from nums\[i\].
    

**Binary Search:**

1. set `l := 0`, `r := queries.length`.
    
2. follow these steps while `l <= r`:
    
    1. set `mid := (l+r)/2`
        
    2. if setting with first `k` queries is able,
        
        * set `ans = k` and `r = mid-1` to try less than `k`.
            
    3. otherwise,
        
        * set `l = mid+1` to try greater than `k`
            

**Line Sweeping:**

1. set `k = 0, sum = 0`
    
2. follow these steps while `i = {0 .. n}`:
    
    1. follow these steps while `sum + diff[i] < nums[i]`:
        
        1. increment `k` by 1. return `-1` if `k` is greater than `queries.length`.
            
        2. update `diff[i]` from `queries[k]`.
            
    2. accumulate `diff[i]` to sum.
        
3. It it valid. so return `k`.
    

## Complexity

**Time Complexity**:

* Binary Search: `O((n+q) * log(q))` - Validation takes `n+q` with validating `log(q)` times.
    
* Line Sweeping: `O(n + q)` - we iterate nums and queries once.
    

**Space Complexity**: `O(n)` - `diff` array stores `n+1` cells.

## Code (C++ | Go)

C++ code is Binary Search code, while golang code uses line sweeping.

```cpp
#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    return 0;
}();

class Solution {
public:
    bool check(int k, vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> diff(n+1);
        for(int i = 0; i < k; i++) {
            diff[queries[i][0]] -= queries[i][2];
            diff[queries[i][1]+1] += queries[i][2];
        }

        int d = 0;
        for(int i = 0; i < n; i++) {
            d += diff[i];
            int x = nums[i] + d;
            if(x > 0) return false;
        }
        return true;
    }
    int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int l = 0;
        int r = queries.size();

        int ans = -1;
        while(l <= r) {
            int mid = (l+r)/2;
            if(check(mid, nums, queries)) {
                ans = mid;
                r = mid-1;
            } else {
                l = mid+1;
            }
        }
        return ans;
    }
};
```

```go
func minZeroArray(nums []int, queries [][]int) int {
    diff := make([]int, len(nums)+1)
    k := 0
    sum := 0
    for i := 0; i < len(nums); i++ {
        for sum + diff[i] < nums[i] {
            k++

            if k > len(queries) {
                return -1
            }

            l, r, v := queries[k-1][0], queries[k-1][1], queries[k-1][2]
            if r >= i {
                diff[max(l, i)] += v
                diff[r+1] -= v
            }
        }
        sum += diff[i]
    }

    return k
}
```