You are given an integer array nums of length n and a 2D array queries, where queries[i] = [li, ri].
For each queries[i]:
[li, ri] in nums.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:
[0, 2] and decrement the values at these indices by 1.[0, 0, 0], which is a Zero Array.Example 2:
Input: nums = [4,3,2,1], queries = [[1,3],[0,2]]
Output: false
Explanation:
[1, 2, 3] and decrement the values at these indices by 1.[4, 2, 1, 0].[0, 1, 2] and decrement the values at these indices by 1.[3, 1, 0, 0], which is not a Zero Array.
Constraints:
1 <= nums.length <= 1050 <= nums[i] <= 1051 <= queries.length <= 105queries[i].length == 20 <= li <= ri < nums.lengthProblem 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.
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.
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.
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.
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.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| 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. |
| Direct Simulation of Operations | Time Complexity: O(n * q), where n is the length of nums and q is the number of queries. |
| Difference Array | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation of Operations | O(n * q) | O(1) | Good for understanding the problem or when constraints are very small |
| Difference Array + Prefix Sum | O(n + q) | O(n) | Best for large inputs with many range queries; converts range updates to constant time |
Zero Array Transformation I | Leetcode 3355 • Techdose • 7,132 views views
Watch 9 more video solutions →Practice Zero Array Transformation I with our built-in code editor and test cases.
Practice on FleetCode