# Zero Array Transformation I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/zero-array-transformation-i)
Canonical: https://scaleengineer.com/dsa/problems/zero-array-transformation-i
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## Problem
You are given an integer array `nums` of length `n` and a 2D array `queries`, where `queries[i] = [li, ri]`.

For each `queries[i]`:

* Select a subset of indices within the range `[li, ri]` in `nums`.
* Decrement the values at the selected indices by 1.

A **Zero Array** is an array where all elements are equal to 0.

Return `true` if it is _possible_ to transform `nums` into a **Zero Array** after processing all the queries sequentially, otherwise return `false`.

**Example 1:**

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

**Output:** true

**Explanation:**

* **For i = 0:**  
  * Select the subset of indices as `[0, 2]` and decrement the values at these indices by 1.
  * The array will become `[0, 0, 0]`, which is a Zero Array.

**Example 2:**

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

**Output:** false

**Explanation:**

* **For i = 0:**  
  * Select the subset of indices as `[1, 2, 3]` and decrement the values at these indices by 1.
  * The array will become `[4, 2, 1, 0]`.
* **For i = 1:**  
  * Select the subset of indices as `[0, 1, 2]` and decrement the values at these indices by 1.
  * The array will become `[3, 1, 0, 0]`, which is not a Zero Array.

**Constraints:**

* `1 <= nums.length <= 105`
* `0 <= nums[i] <= 105`
* `1 <= queries.length <= 105`
* `queries[i].length == 2`
* `0 <= li <= ri < nums.length`

# Approaches
## Brute Force Approach
This approach directly calculates the total number of times each element can be decremented. It iterates through every query and, for each element within the query's range `[l, r]`, it increments a counter. After counting the available decrements for all elements, it compares these counts with the initial values in the `nums` array.
**Time:** O(N * Q), where N is the length of `nums` and Q is the number of queries. For each of the Q queries, we might iterate up to N elements. · **Space:** O(N), where N is the length of the `nums` array. This space is used for the `counts` array.
**Pros:** The logic is straightforward and easy to follow.; It's simple to implement.
**Cons:** The time complexity is high due to the nested loops, making it unsuitable for large inputs.; It will likely result in a 'Time Limit Exceeded' error on platforms with strict time limits for the given constraints.
### Explanation
The fundamental insight is that for the array to become a zero array, each element `nums[i]` must be decremented exactly `nums[i]` times. The problem allows us to decrement a subset of elements within a given range `[l, r]` for each query. This means for any query covering index `i`, we have the option to decrement `nums[i]`. Therefore, the total number of times `nums[i]` can possibly be decremented is the total number of queries whose ranges include `i`.

This brute-force approach calculates this total for each index. 

1.  We create an auxiliary array, `counts`, of the same size as `nums`, initialized to zeros. This array will store the total number of queries covering each index.
2.  We loop through each query `[l, r]`. For each query, we loop again from `l` to `r` and increment `counts[i]` for each `i` in this range.
3.  After the loops complete, `counts[i]` holds the maximum number of times `nums[i]` can be decremented.
4.  Finally, we perform a check. We iterate from `i = 0` to `n-1` and compare `nums[i]` with `counts[i]`. If `nums[i] > counts[i]`, it's impossible to reduce `nums[i]` to zero, so we return `false`. If we finish the loop, it means every element has enough available decrements, and we return `true`.

```java
class Solution {
    public boolean isPossible(int n, int[] nums, int[][] queries) {
        int[] counts = new int[n];
        for (int[] query : queries) {
            int l = query[0];
            int r = query[1];
            for (int i = l; i <= r; i++) {
                counts[i]++;
            }
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] > counts[i]) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
- Initialize an integer array `counts` of size `n` with all elements set to 0.
- Iterate through each `query` in the `queries` array. Let the query be `[l, r]`.
- For each query, iterate from index `i = l` to `r`.
- In the inner loop, increment `counts[i]` by 1.
- After processing all queries, iterate from `i = 0` to `n-1`.
- For each index `i`, check if `nums[i]` is greater than `counts[i]`.
- If the condition `nums[i] > counts[i]` is true for any `i`, it's impossible to make that element zero. Return `false`.
- If the loop completes without returning, it means it's possible for all elements. Return `true`.

## Difference Array and Prefix Sum
This optimized approach avoids the costly nested loops by using a difference array. Instead of incrementing the count for every element in a query's range, we mark the start of the range with a `+1` and the position after the end of the range with a `-1`. A single pass over this difference array can then reveal the actual count for each element by maintaining a running sum. This reduces the time complexity significantly.
**Time:** O(N + Q), where N is the length of `nums` and Q is the number of queries. We iterate through queries once (O(Q)) and then through the `nums` array once (O(N)). · **Space:** O(N), where N is the length of the `nums` array. This space is for the `diff` array.
**Pros:** Highly efficient with a linear time complexity.; Optimal solution that passes for large constraints.
**Cons:** Requires understanding of the difference array or prefix sum concept, making it slightly less intuitive than the brute-force method.
### Explanation
The bottleneck in the brute-force approach is re-calculating counts for overlapping query ranges. The difference array technique is perfect for handling such range-based updates efficiently.

The logic remains the same: we need to find the total number of queries covering each index `i` and check if it's at least `nums[i]`. Here's how we do it efficiently:

1.  Create a difference array, `diff`, of size `n`, initialized to zeros.
2.  Iterate through each query `[l, r]`. An increment over the range `[l, r]` can be recorded by adding 1 at the start (`diff[l]++`) and subtracting 1 just after the end (`diff[r+1]--`). The subtraction at `r+1` cancels the effect of the initial increment for all subsequent indices.
3.  After processing all queries in `O(Q)` time, the `diff` array is prepared. The actual count for any index `i` is the sum of all `diff[j]` for `j <= i` (the prefix sum).
4.  We can calculate these prefix sums and check the condition against `nums` in a single pass. We initialize a variable `current_coverage = 0`. We then iterate from `i = 0` to `n-1`. In each step, we add `diff[i]` to `current_coverage`. This `current_coverage` now holds the total number of queries covering index `i`. We immediately compare it with `nums[i]`. If `nums[i] > current_coverage`, we return `false`.
5.  If this loop finishes, it's possible to make the array all zeros, so we return `true`.

This method combines the calculation of counts and the final check into one efficient pass.

```java
class Solution {
    public boolean isPossible(int n, int[] nums, int[][] queries) {
        int[] diff = new int[n];
        for (int[] query : queries) {
            int l = query[0];
            int r = query[1];
            diff[l]++;
            if (r + 1 < n) {
                diff[r + 1]--;
            }
        }

        int current_coverage = 0;
        for (int i = 0; i < n; i++) {
            current_coverage += diff[i];
            if (nums[i] > current_coverage) {
                return false;
            }
        }

        return true;
    }
}
```
### Algorithm
- Initialize an integer array `diff` of size `n` with all elements set to 0.
- Iterate through each `query` in the `queries` array. Let the query be `[l, r]`.
- For each query, increment `diff[l]` by 1.
- If `r + 1` is less than `n`, decrement `diff[r + 1]` by 1.
- After processing all queries, create a `current_coverage` variable, initialized to 0.
- Iterate from `i = 0` to `n-1`:
  - Update `current_coverage` by adding `diff[i]`. This gives the total query coverage for index `i`.
  - Check if `nums[i]` is greater than `current_coverage`.
  - If it is, return `false`.
- If the loop completes, return `true`.

# Solutions
### Java

```java
class Solution { public boolean isZeroArray ( int [] nums , int [][] queries ) { int n = nums . length ; int [] d = new int [ n + 1 ]; for ( var q : queries ) { int l = q [ 0 ], r = q [ 1 ]; ++ d [ l ]; -- d [ r + 1 ]; } 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: bool isZeroArray ( vector < int >& nums , vector < vector < int >>& queries ) { int n = nums . size (); int d [ n + 1 ]; memset ( d , 0 , sizeof ( d )); for ( const auto & q : queries ) { int l = q [ 0 ], r = q [ 1 ]; ++ d [ l ]; -- d [ r + 1 ]; } for ( int i = 0 , s = 0 ; i < n ; ++ i ) { s += d [ i ]; if ( nums [ i ] > s ) { return false ; } } return true ; } };
```

### Python

```python
class Solution : def isZeroArray ( self , nums : List [ int ], queries : List [ List [ int ]]) -> bool : d = [ 0 ] * ( len ( nums ) + 1 ) for l , r in queries : d [ l ] += 1 d [ r + 1 ] -= 1 s = 0 for x , y in zip ( nums , d ): s += y if x > s : return False return True
```