Skip to main content
Talentd

Zero Array Transformation I - Solution & Explanation

MediumArrayPrefix Sum16 min readAsked at: Amazon, Microsoft, Chubb +2
Practice this problem

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.

 

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

Approach Overview

Problem Overview: You are given an integer array nums and several range queries. Each query allows decreasing every element in the interval [l, r] by 1 exactly once. The goal is to determine whether these operations provide enough decrements to reduce every value in nums to zero without running out of operations for any index.

Approach 1: Direct Simulation of Operations (O(n * q) time, O(1) space)

The straightforward idea is to simulate every query exactly as described. For each query [l, r], iterate through the range and decrement the corresponding elements in nums. After processing all queries, check whether every element became zero. This approach mirrors the problem statement and is useful for validating logic on small inputs.

The drawback is performance. If the array size is n and the number of queries is q, repeatedly iterating across ranges leads to O(n * q) time in the worst case. Large inputs quickly make this approach too slow. It also mutates the original array, which may require copying if the input must be preserved.

Approach 2: Efficient Interval Update using Difference Array (O(n + q) time, O(n) space)

A more scalable solution focuses on counting how many decrement operations are available for each index instead of applying them directly. Each query contributes one potential decrement to every element in its range. Using a difference array, mark +1 at l and -1 at r + 1. After processing all queries, compute a prefix sum to determine how many operations cover each index.

This converts multiple range updates into constant‑time operations. The prefix sum pass reconstructs the total number of decrements available at every position. If the coverage count at index i is less than nums[i], the element cannot reach zero because it lacks enough decrement operations. If every index has sufficient coverage, the transformation is possible.

This technique relies on the classic prefix sum pattern combined with interval marking from the array toolkit. It avoids repeated range iteration and processes the entire input in linear time.

Recommended for interviews: The difference array approach is the expected solution. Interviewers look for the observation that queries only contribute counts of operations, not the actual decrements themselves. Implementing the prefix accumulation demonstrates strong understanding of prefix sums and efficient range updates. Starting with the simulation approach can help explain the intuition before optimizing to the linear-time solution.

Approach 1: Efficient Interval Update using Difference Array

This approach utilizes the concept of difference arrays to efficiently apply the operations for each query range. Instead of decrementing elements directly, we apply the operations incrementally over the range, which allows us to keep track of cumulative changes.

The solution uses a 'delta' array to apply increments and decrements at specific points, which is very efficient for range update operations. For each query, we decrement the starting index of the range by 1 and increment the position just after the end of the range by 1. Then, we propagate these effects across the 'nums' array using a cumulative carry. Finally, we check if every element in the final array is zero or not.

Code

PythonJavaScriptC++CJavaC#

Python

JavaScript

C++

C

Java

C#

Complexity

Time Complexity: O(n + q), where n is the length of nums and q is the number of queries.
Space Complexity: O(n), for the delta array used in the implementation.

Try this approach in the editor →

Approach 2: Direct Simulation of Operations

This approach directly applies decrement operations specified by each query to the range given. Though simple to understand, it may not be efficient for large input sizes due to the repetitive operations. Consider optimizing if the constraints are strict.

This solution directly walks over each query range and decrements the values if they are greater than zero. After all queries, it checks if every element is zero. This is not time efficient for large datasets but is straightforward to understand and serves as a baseline approach.

Code

PythonJavaScriptC++CJavaC#

Python

JavaScript

C++

C

Java

C#

Complexity

Time Complexity: O(n * q), where n is the length of nums and q is the number of queries.
Space Complexity: O(1), no extra space is used except input.

Try this approach in the editor →

Approach 3: Difference Array

We can use a difference array to solve this problem.

Define an array d of length n + 1, with all initial values set to 0. For each query [l, r], we add 1 to d[l] and subtract 1 from d[r + 1].

Then we traverse the array d within the range [0, n - 1], accumulating the prefix sum s. If nums[i] > s, it means nums cannot be converted to a zero array, so we return false.

After traversing, return true.

The time complexity is O(n + m), and the space complexity is O(n). Here, n and m are the lengths of the array nums and the number of queries, respectively.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Efficient Interval Update using Difference Array

Time Complexity: O(n + q), where n is the length of nums and q is the number of queries.
Space Complexity: O(n), for the delta array used in the implementation.

Direct Simulation of Operations

Time Complexity: O(n * q), where n is the length of nums and q is the number of queries.
Space Complexity: O(1), no extra space is used except input.

Difference Array—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct Simulation of OperationsO(n * q)O(1)Good for understanding the problem or when constraints are very small
Difference Array + Prefix SumO(n + q)O(n)Best for large inputs with many range queries; converts range updates to constant time

Video Solution

Zero Array Transformation I | Leetcode 3355 • Techdose • 7,255 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Zero Array Transformation I easy or hard?
Zero Array Transformation I is rated Medium because the naive simulation is simple but inefficient. Recognizing that the problem only requires counting how many operations affect each index leads to the optimal difference array and prefix sum solution.
Zero Array Transformation I Python/Java solution
Python and Java implementations typically build a difference array of size n + 1. Each query updates diff[l] += 1 and diff[r + 1] -= 1, followed by a prefix sum sweep to compute coverage. The final check compares coverage[i] with nums[i] to confirm whether all elements can be reduced to zero.
How to solve Zero Array Transformation I in O(n)?
Process each query using a difference array by adding +1 at the start index and −1 after the end index. After all queries are recorded, compute a prefix sum to determine how many operations cover each position. Compare that count with nums[i]; if the available operations are less than the required decrements, the transformation is impossible.
What is the best approach for Zero Array Transformation I?
The optimal approach uses a difference array combined with a prefix sum. Instead of applying every decrement operation directly, each query contributes one operation to its range. After computing prefix sums, you know how many decrements are available at each index. If that count is at least nums[i] for every position, the array can be reduced to zero in O(n + q) time.
Is Zero Array Transformation I asked at Google/Amazon/Meta?
Problems involving range updates, difference arrays, and prefix sums appear frequently in interviews at companies like Amazon, Google, and Meta. Variants of this question test whether candidates recognize when to replace repeated range updates with a prefix-sum based technique.
What data structure is used in Zero Array Transformation I?
The key structure is a difference array, which supports constant-time range updates. A prefix sum pass converts this structure into the number of operations covering each index, allowing an efficient check against the required decrements in nums.
What is the time complexity of Zero Array Transformation I?
The optimal solution runs in O(n + q) time, where n is the array length and q is the number of queries. Each query updates the difference array in constant time, and a single prefix sum pass reconstructs the coverage for every index.

Ready to solve this problem?

Practice Zero Array Transformation I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Zero Array Transformation IV