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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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

Similar Problem

Zero Array Transformation 2 Zero Array Transformation 3

Solution

Method 1 - Efficient Range Decrements Using Delta Array

The challenge is to determine if we can turn all elements of nums into 0 using the given queries. Directly applying each query to nums would be inefficient (O(n × q)). Instead, we leverage a delta array to efficiently manage range operations:

  1. Use the delta array to record where range decrements start and stop.
  2. Calculate the cumulative effect of delta values on nums in a single pass, allowing us to apply all queries efficiently.
  3. If at any index, the total decrements (nums[i] + cumulative changes) are insufficient to make nums[i] <= 0, return False.

Approach

  1. Delta Array for Efficient Range Updates:

    • For each query [start, end], update delta[start] -= 1 (start a decrement) and delta[end + 1] += 1 (stop the decrement after end).

  2. Cumulative Changes:

    • Use a cumulative sum (total_possible_change) to apply all range effects while iterating through nums.
    • Check if nums[i] + total_possible_change > 0 at any index. If true, return False.

  3. Final Verification:

    • If we process all indices without failure, return True.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public boolean isZeroArray(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] delta = new int[n]; // Auxiliary array for range updates

        // Process queries to populate the delta array
        for (int[] query : queries) {
            int start = query[0], end = query[1];
            delta[start]--; // Decrease at the start of the range
            if (end + 1 < n) {
                delta[end + 1]++; // Offset after the end of the range
            }
        }

        // Apply delta and process nums
        int totalPossibleChange = 0;
        for (int i = 0; i < n; i++) {
            totalPossibleChange += delta[i]; // Cumulative sum of range effects
            if (nums[i] + totalPossibleChange > 0) { // Check if transformation to zero is possible
                return false;
            }
        }

        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def isZeroArray(self, nums: List[int], queries: List[List[int]]) -> bool:
        n = len(nums)
        delta = [0] * n  # Auxiliary array for range updates

        # Process queries to populate the delta array
        for start, end in queries:
            delta[start] -= 1  # Decrease at the start of the range
            if end + 1 < n:
                delta[end + 1] += 1  # Offset after the end of the range

        # Apply delta and process nums
        total_possible_change = 0
        for i in range(n):
            total_possible_change += delta[i]  # Cumulative sum of range effects
            if nums[i] + total_possible_change > 0:  # Check if transforming to zero is possible
                return False

        return True

Complexity

  • ⏰ Time complexity: O(n + q)
    • Processing queries: O(q) for q queries to populate the delta array.
    • Validating array: O(n) iterating through nums to apply the total possible changes.
    • Total: O(n + q).
  • 🧺 Space complexity: O(n) for using delta array

Dry Run

  1. Initial Delta Array:
    • delta = [0, 0, 0].
  2. Processing Query [0, 2]:
    • delta[0] -= 1 → delta = [-1, 0, 0].
    • delta[3] cannot be updated as it is out of bounds.
  3. Applying Delta:
    • At i = 0: total_possible_change = -1, nums[0] = 1 + (-1) = 0.
    • At i = 1: total_possible_change = -1, nums[1] = 0 + (-1) = -1 (valid since it’s ≤ 0).
    • At i = 2: total_possible_change = -1, nums[2] = 1 + (-1) = 0.
  4. Final Check:
    • nums = [0, 0, 0] → Return True.