Zero Array Transformation I

medium array prefix sum difference array

Problem

You are given an array nums and a list of queries, where each queries[i] = [l, r]. For each query you may pick any subset of indices inside [l, r] and decrement each picked value by 1. After running all queries in order, return true if every element can be made 0.

Because the subset is free per query, index i can be zeroed exactly when the number of queries whose range covers i is at least nums[i]. So the answer is true iff nums[i] ≤ coverage[i] for all i.

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

Outputtrue

The single query covers indices 0..2 once each, so coverage = [1,1,1] ≥ nums = [1,0,1]. All can reach 0.

nums (comma-separated)

queries (l:r, comma-separated)

def isZeroArray(nums, queries):
    n = len(nums)
    diff = [0] * (n + 1)            # difference array
    for l, r in queries:
        diff[l] += 1               # +1 where coverage starts
        diff[r + 1] -= 1           # -1 just past where it ends
    cover = 0
    for i in range(n):
        cover += diff[i]           # prefix sum = times index i is covered
        if nums[i] > cover:        # not enough decrements available
            return False
    return True

function isZeroArray(nums, queries) {
  const n = nums.length;
  const diff = new Array(n + 1).fill(0);   // difference array
  for (const [l, r] of queries) {
    diff[l] += 1;                          // +1 where coverage starts
    diff[r + 1] -= 1;                       // -1 just past where it ends
  }
  let cover = 0;
  for (let i = 0; i < n; i++) {
    cover += diff[i];                       // prefix sum = coverage of i
    if (nums[i] > cover) return false;       // not enough decrements
  }
  return true;
}

boolean isZeroArray(int[] nums, int[][] queries) {
    int n = nums.length;
    int[] diff = new int[n + 1];          // difference array
    for (int[] q : queries) {
        diff[q[0]] += 1;                  // +1 where coverage starts
        diff[q[1] + 1] -= 1;              // -1 just past where it ends
    }
    int cover = 0;
    for (int i = 0; i < n; i++) {
        cover += diff[i];                 // prefix sum = coverage of i
        if (nums[i] > cover) return false; // not enough decrements
    }
    return true;
}

bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
    int n = nums.size();
    vector<int> diff(n + 1, 0);            // difference array
    for (auto& q : queries) {
        diff[q[0]] += 1;                  // +1 where coverage starts
        diff[q[1] + 1] -= 1;              // -1 just past where it ends
    }
    int cover = 0;
    for (int i = 0; i < n; i++) {
        cover += diff[i];                 // prefix sum = coverage of i
        if (nums[i] > cover) return false; // not enough decrements
    }
    return true;
}

Explanation

The trick is realizing that the order of queries and the freedom to pick any subset don't actually matter for feasibility. Within a query [l, r] you can decrement each index independently, so the only thing that limits index i is how many queries cover it. If that count reaches nums[i], you can decrement i exactly nums[i] times (and skip it in the rest). If it falls short, i can never reach 0.

So the problem reduces to: for every index i, is coverage[i] ≥ nums[i]? Computing coverage naively by looping over each query's whole range would be O(queries · n) — too slow for 10⁵ of each.

A difference array turns each range update into two point updates. For a query [l, r] we do diff[l] += 1 and diff[r+1] -= 1. The +1 opens coverage at l; the -1 closes it just after r.

Sweeping a prefix sum across diff reconstructs the coverage count at each index: cover += diff[i] gives exactly how many queries include i. We compare against nums[i] on the fly and bail out the moment some index is undercovered.

Example: nums = [4,3,2,1], queries = [[1,3],[0,2]]. Coverage works out to [1,2,2,1]. Index 0 needs 4 but is covered only once, so the answer is false.

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