Zero Array Transformation II

medium two pointers difference array prefix sum

Problem

You are given an array nums and a list of queries, where each queries[i] = [l, r, val] lets you decrement every index in [l, r] by at most val (the amount is chosen independently per index). Processing the first k queries in order, return the minimum non-negative k after which nums can become all zeros. If impossible, return -1.

Inputnums = [2,0,2], queries = [[0,2,1],[0,2,1],[1,1,3]]

Output2

After 2 queries, indices 0 and 2 each receive 1 + 1 = 2 of available decrement, so [2,0,2] can reach [0,0,0].

nums (comma-separated)

queries (l:r:val, comma-separated)

def minZeroArray(nums, queries):
    n = len(nums)
    diff = [0] * (n + 1)        # difference array for range decrements
    k = 0                       # how many queries consumed (the answer)
    running = 0                 # decrement available at the current index
    for i in range(n):
        running += diff[i]      # extend prefix sum into index i
        # pull in queries until index i can drop to 0
        while running < nums[i] and k < len(queries):
            l, r, val = queries[k]
            k += 1
            if r < i:
                continue        # this query does not cover index i
            start = max(l, i)
            diff[start] += val
            diff[r + 1] -= val
            if start == i:
                running += val  # affects the current index right away
        if running < nums[i]:
            return -1           # even all queries cannot zero index i
    return k

function minZeroArray(nums, queries) {
  const n = nums.length;
  const diff = new Array(n + 1).fill(0); // difference array
  let k = 0;            // queries consumed (the answer)
  let running = 0;      // decrement available at current index
  for (let i = 0; i < n; i++) {
    running += diff[i]; // extend prefix sum into index i
    // pull in queries until index i can drop to 0
    while (running < nums[i] && k < queries.length) {
      const [l, r, val] = queries[k];
      k++;
      if (r < i) continue; // does not cover index i
      const start = Math.max(l, i);
      diff[start] += val;
      diff[r + 1] -= val;
      if (start === i) running += val; // hits current index now
    }
    if (running < nums[i]) return -1;  // cannot zero index i
  }
  return k;
}

int minZeroArray(int[] nums, int[][] queries) {
    int n = nums.length;
    int[] diff = new int[n + 1];   // difference array
    int k = 0;                     // queries consumed (the answer)
    long running = 0;              // decrement available at index i
    for (int i = 0; i < n; i++) {
        running += diff[i];        // extend prefix sum into index i
        // pull in queries until index i can drop to 0
        while (running < nums[i] && k < queries.length) {
            int l = queries[k][0], r = queries[k][1], val = queries[k][2];
            k++;
            if (r < i) continue;   // does not cover index i
            int start = Math.max(l, i);
            diff[start] += val;
            diff[r + 1] -= val;
            if (start == i) running += val; // hits current index now
        }
        if (running < nums[i]) return -1;   // cannot zero index i
    }
    return k;
}

int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
    int n = nums.size();
    vector<long long> diff(n + 1, 0); // difference array
    int k = 0;                       // queries consumed (the answer)
    long long running = 0;           // decrement available at index i
    for (int i = 0; i < n; i++) {
        running += diff[i];          // extend prefix sum into index i
        // pull in queries until index i can drop to 0
        while (running < nums[i] && k < (int)queries.size()) {
            int l = queries[k][0], r = queries[k][1], val = queries[k][2];
            k++;
            if (r < i) continue;     // does not cover index i
            int start = max(l, i);
            diff[start] += val;
            diff[r + 1] -= val;
            if (start == i) running += val; // hits current index now
        }
        if (running < nums[i]) return -1;   // cannot zero index i
    }
    return k;
}

Explanation

Each query offers up to val units of decrement to every index in [l, r]. To zero out index i we just need the total available decrement landing on i (summed over the queries we have processed) to reach nums[i] — the per-index freedom means any surplus is harmless.

So the task reduces to: scan indices left to right; for index i keep a value running = how much decrement the consumed queries provide here. If running is still below nums[i], we are forced to consume more queries (advance the pointer k) until it catches up.

Applying a query naively over a whole range is too slow, so we use a difference array diff: adding val at start and subtracting it at r + 1 records a range update in O(1). The prefix sum of diff reconstructs the decrement at each index as we sweep, which is exactly what running += diff[i] does.

Because index i never needs a query whose right end r is before i (and earlier indices already pulled in everything they needed), the query pointer k only moves forward — a classic two-pointer sweep. When a newly consumed query starts exactly at i (start == i), its val must be folded into running immediately.

If we exhaust every query and some index still has running < nums[i], no k works, so we return -1. Otherwise k — the number of queries we had to consume — is the minimum answer. If nums is already all zeros, the loop never advances k and the answer is 0.

Example: nums = [2,0,2]. Index 0 needs 2; queries 0 and 1 each add 1, reaching 2 after consuming 2 queries. Index 1 needs 0 (already satisfied). Index 2 needs 2 and already has 1 + 1 = 2 from those same queries. So k = 2.

Time: O(n + q) Space: O(n)