🌱 Keegan's Digital Garden

3355. Zero Array Transformation I

2 min read

📝 Problem Details

input array nums of length n input 2d array queries where queries[i] = [l,r] for each queries[i] you can: select a subset of indices within the range l,r in nums decrement the values at the selected indices by 1

return true if it is possible to transform nums into a zero array after processing all queries sequentially, otherwise return false

💭What Were My Initial Thoughts?

- we could brute force each query and decrement all values in the range
- this would be too slow / inefficient (O(n * q))

Key Idea: Use a Difference Array

  • Instead of modifying nums directly, we use a difference array to track incremental changes efficiently.
  • A difference array helps apply range updates in O(1) time.
  • After processing all queries, we check if nums can reach all 0s by applying accumulated changes.

Steps:

  1. Create a difference array diff of size n+1 (to handle range updates).
  2. Process each query [li, ri]:
    • Decrement diff[li] by 1 (starting the decrement at li).
    • Increment diff[ri + 1] by 1 (restoring values beyond ri).
  3. Apply the difference array to nums:
    • Compute prefix sums to get the actual transformed array.
  4. Check if all elements in nums are 0.

💡 Explanation of Solution

Difference Array approach:

1. create a difference array diff of size n+1 (to handle range updates)

2. process each query [l,r]
	- decrement diff[l] by 1 (start the decrement at l)
	- increment diff[r+1] by 1 (restoring values beyong r)

3. apply the difference array to nums
	- compute prefix sums to get the actual transformed array

4. check if all elements in nums are 0

⌛ Complexity Analysis

Time Complexity: O(n + q)

Space Complexity: O(n)

💻 Implementation of Solution

class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
 
        vector<int> diff(n+1, 0);
 
        // process all queries using difference array
        for(const auto& q : queries) {
            int li = q[0], ri = q[1];
            diff[li] -= 1;
            diff[ri+1] += 1;
        }
 
        // apply the difference array to nums
        int currDecrement = 0;
        for(int i=0; i < n; i++) {
            currDecrement += diff[i]; // accumulate decrement effect
            nums[i] += currDecrement;
 
            // if any value is still positive return false
            if(nums[i] > 0) return false;
        }
 
        return true;
    }
};

Graph View