Zero Array Transformation I - Practice Coding Problems

Zero Array Transformation I - Problem

You are given an integer array nums of length n and a 2D array queries, where queries[i] = [l_i, r_i].

For each queries[i]:

Select a subset of indices within the range [l_i, r_i] 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.

Input & Output

Example 1 — Basic Case

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

› Output: false

💡 Note: Position 3 has value 4 but only 1 query can affect it (query [1,3]), so it cannot be reduced to 0

Example 2 — Possible Transformation

$ Input: nums = [1,0,1], queries = [[0,2]]

› Output: true

💡 Note: Single query [0,2] can decrement positions 0 and 2 once each, making array [0,0,0]

Example 3 — Edge Case

$ Input: nums = [0,0,0], queries = []

› Output: true

💡 Note: Array is already all zeros, no queries needed

Constraints

1 ≤ nums.length ≤ 10⁵
0 ≤ nums[i] ≤ 10⁵
1 ≤ queries.length ≤ 10⁵
queries[i].length == 2
0 ≤ l_i ≤ r_i < nums.length

Visualization

Tap to expand

Understanding the Visualization

Input

Array nums and query ranges that can decrement positions

Process

Count how many queries can affect each position

Output

Check if coverage is sufficient to zero out all positions

Key Takeaway

🎯 Key Insight: Each position must have coverage count >= its value to be reducible to zero

Asked in

G Google 12 a Amazon 8 M Microsoft 6 f Meta 4

The key insight is that each position needs sufficient coverage from overlapping query ranges to be decremented to zero. The optimal approach uses a difference array to efficiently count how many queries can affect each position, then validates if this coverage is sufficient. Time: O(n + q), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Prefix Sum Optimization	O(n + q)	O(n)	Calculate maximum possible decrements for each position using prefix sum technique
Difference Array (Optimal)	O(n + q)	O(n)	Use difference array technique to efficiently count query coverage in O(n + q) time
Brute Force Simulation	O(2^(n*q))	O(q)	Simulate all possible ways to apply each query and check if nums can become zero

Prefix Sum Optimization — Algorithm Steps

Count how many queries can affect each position
For each position, the maximum decrements possible equals the number of covering queries
Check if max decrements >= original value for all positions

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Coverage

For each position, count how many queries can affect it

Compare Values

Check if coverage count >= original value at each position

Result

Return true if all positions have sufficient coverage

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(int* nums, int n, int queries[][2], int q) {
    int* maxDecrements = calloc(n, sizeof(int));
    
    // Count how many queries can affect each position
    for (int i = 0; i < q; i++) {
        int l = queries[i][0], r = queries[i][1];
        for (int j = l; j <= r; j++) {
            maxDecrements[j]++;
        }
    }
    
    // Check if each position can be reduced to zero
    for (int i = 0; i < n; i++) {
        if (maxDecrements[i] < nums[i]) {
            free(maxDecrements);
            return false;
        }
    }
    
    free(maxDecrements);
    return true;
}

int main() {
    // Simple test case
    int nums[] = {2, 1, 3, 4};
    int queries[][2] = {{1, 2}, {1, 3}, {0, 1}};
    bool result = solution(nums, 4, queries, 3);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + q)

Single pass through nums array and queries array

✓ Linear Growth

Space Complexity

O(n)

Array to store maximum possible decrements for each position

⚡ Linearithmic Space

9.0K Views

Medium Frequency

~15 min Avg. Time

234 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Prefix Sum Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler