Problem Statement

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.

LeetCode

• https://leetcode.com/problems/zero-array-transformation-i/?envType=daily-question&envId=2025-05-20

Constraints

1 <= nums.length <= 10^5
0 <= nums[i] <= 10^5
1 <= queries.length <= 10^5
queries[i].length == 2
0 <= li <= ri < nums.length

Examples

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.

Different Approaches

1️⃣ Brute Force Approach (TLE)

Code:

class Solution {
public:
    // Function to determine if all elements in nums become 0 after applying the queries
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {

        // Loop through each query in the list of queries
        for (auto query : queries) {
            // Each query contains two integers: start and end index
            int startIndex = query[0];
            int endIndex = query[1];

            // For each index in the range [startIndex, endIndex], decrease the number by 1 if it's not already 0
            for (int i = startIndex; i <= endIndex; i++) {
                if (nums[i] != 0) {
                    nums[i]--;  // Decrease the value at index i by 1
                }
                // If the value is already 0, we leave it as-is (we don't go into negative values)
            }
        }

        // After applying all queries, check if all values in nums are 0
        for (auto elm : nums) {
            if (elm != 0) return false;  // If we find any value that is not 0, return false
        }

        // If we finish the loop without returning false, that means all values are 0
        return true;
    }
};

Complexity Analysis:

• Time Complexity:O(q * n)
  • n = size of nums
  • q = number of queries
  • Worst-case: Each query can touch up to n elements (if startIndex = 0 and endIndex = n - 1)
  • Therefore, in the worst case, the inner loop runs O(n) times per query.
  • So the total work done for all queries is:
    • O(q * n)
• Space Complexity:O(1)

2️⃣ Difference Array Technique (Optimal Approach)

Code:

class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {

        // Step 1: Get the size of the input array
        int n = nums.size();

        // Step 2: Create a difference array initialized with 0s
        // This will help us efficiently apply range-based increment operations
        vector<int> difference(n, 0);

        // Step 3: Process each query to update the difference array
        for (auto query: queries) {
            int startIndex = query[0];
            int endIndex = query[1];

            // Mark the start of the decrement range
            difference[startIndex]++;

            // Mark the end of the decrement range (cancel effect after endIndex)
            if (endIndex + 1 < n) {
                difference[endIndex + 1]--;
            }
        }

        // Step 4: Apply prefix sum on the difference array
        // This gives us how many times each index was targeted by queries
        vector<int> result(n, 0); // This will hold the number of times each index is decremented
        int cummulativeSum = 0;   // Running total to compute prefix sum

        for (int i = 0; i < n; i++) {
            cummulativeSum += difference[i]; // Add current difference
            result[i] = cummulativeSum;      // Store number of times this index is decremented
        }

        // Step 5: Check if each number in the original array can be zeroed
        for (int i = 0; i < n; i++) {
            // If the number of decrements is less than the original value,
            // it means we couldn't reduce it to zero
            if (nums[i] > result[i]) return false;
        }

        // Step 6: If all numbers can be reduced to zero, return true
        return true;
    }
};

Complexity Analysis:

• Time Complexity: O(n + q)
  • O(q): to process all queries
  • O(n): for prefix sum and final comparison
• Space Complexity: O(n)
  • difference and result arrays of size n