Skip to main content
Talentd

Zero Array Transformation II - Solution & Explanation

MediumArrayBinary SearchPrefix Sum25 min readAsked at: Amazon, Meta, Uber +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, vali].

Each queries[i] represents the following action on nums:

  • Decrement the value at each index in the range [li, ri] in nums by at most vali.
  • The amount by which each value is decremented can be chosen independently for each index.

A Zero Array is an array with all its elements equal to 0.

Return the minimum possible non-negative value of k, such that after processing the first k queries in sequence, nums becomes a Zero Array. If no such k exists, return -1.

 

Example 1:

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

Output: 2

Explanation:

  • For i = 0 (l = 0, r = 2, val = 1):
    • Decrement values at indices [0, 1, 2] by [1, 0, 1] respectively.
    • The array will become [1, 0, 1].
  • For i = 1 (l = 0, r = 2, val = 1):
    • Decrement values at indices [0, 1, 2] by [1, 0, 1] respectively.
    • The array will become [0, 0, 0], which is a Zero Array. Therefore, the minimum value of k is 2.

Example 2:

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

Output: -1

Explanation:

  • For i = 0 (l = 1, r = 3, val = 2):
    • Decrement values at indices [1, 2, 3] by [2, 2, 1] respectively.
    • The array will become [4, 1, 0, 0].
  • For i = 1 (l = 0, r = 2, val = 1):
    • Decrement values at indices [0, 1, 2] by [1, 1, 0] respectively.
    • The array will become [3, 0, 0, 0], which is not a Zero Array.

 

Constraints:

  • 1 <= nums.length <= 105
  • 0 <= nums[i] <= 5 * 105
  • 1 <= queries.length <= 105
  • queries[i].length == 3
  • 0 <= li <= ri < nums.length
  • 1 <= vali <= 5

Approach Overview

Problem Overview: You are given an integer array nums and a list of range queries. Each query allows decreasing every element in a subarray by a certain value. The task is to determine the minimum number of queries (in order) required so that every element in nums becomes zero or negative. If it is impossible even after all queries, return -1.

Approach 1: Brute Force Simulation (O(n * m) time, O(1) space)

The direct approach applies queries one by one and updates the affected range in the array. For each query [l, r, val], iterate from l to r and subtract val from each element. After applying a query, scan the array to check if all values are <= 0. If so, return the number of queries used so far. This approach clearly shows the mechanics of the problem but becomes slow when both the array length and number of queries are large because every query touches up to n elements.

Approach 2: Binary Search + Difference Array (O((n + m) log m) time, O(n) space)

The key observation is that queries are applied in order, and we only care about the earliest prefix of queries that can reduce every index enough. This makes the problem monotonic: if the first k queries can zero the array, any k+1 queries will also work. That property allows binary search over the number of queries.

To efficiently evaluate whether the first k queries are sufficient, use a difference array for range updates. For each query [l, r, val], add val at diff[l] and subtract it at diff[r+1]. After processing the first k queries, compute the prefix sum to obtain the total decrement available for each index. If the accumulated decrement at index i is at least nums[i], that element can be reduced to zero. Otherwise, the first k queries are insufficient.

This technique converts repeated range updates into O(1) operations and a single prefix sum sweep. It leverages ideas from prefix sums and efficient range updates commonly used in array problems.

Recommended for interviews: The binary search + difference array approach is the expected solution. The brute force simulation demonstrates understanding of the operations, but it does not scale. Interviewers typically look for recognition of the monotonic condition and the use of a difference array to process range updates efficiently.

Approach 1: Brute Force Approach

In this approach, we will iterate through each query and update the array accordingly by decrementing each value in the specified range by the given value in the query. This method directly simulates applying each query to the array.

The C solution iteratively applies each query to the nums array. For each query, it updates the values in the range [l, r] by decrementing them by val, ensuring no negative values occur. After each query application, nums is checked to see if it is entirely zeros, at which point the index of the current query (incremented by one for a 1-based position) is returned as the result. If no such condition is met by the end of all queries, it returns -1.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n * m), where n is the length of nums and m is the number of queries. Each query may require iterating over the entire range of the array.
Space Complexity: O(1), since all modifications are done in place.

Try this approach in the editor →

Approach 2: Difference Array Approach for Range Update

This approach utilizes a difference array to optimize range updates. Instead of manually applying the decrement to each element between l and r, we will maintain a difference array where each query updates only the boundary indices. After processing all queries, the difference array is used to decrement the original array and check for the Zero Array condition efficiently.

The C solution uses a difference array to efficiently handle range decrements. Instead of decrementing each element directly, it adjusts the boundaries using the difference array and then applies the accumulated changes across nums to verify if it becomes a Zero Array. This integration of differential logic reduces the operational size for each query application.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n + m), where n is the length of nums and m is the number of queries, optimizing the brute-force complexity significantly.
Space Complexity: O(n), for the difference array storage.

Try this approach in the editor →

Approach 3: Difference Array + Binary Search

We notice that the more queries we use, the easier it is to turn the array into a zero array, which shows monotonicity. Therefore, we can use binary search to enumerate the number of queries and check whether the array can be turned into a zero array after the first k queries.

We define the left boundary l and right boundary r for binary search, initially l = 0, r = m + 1, where m is the number of queries. We define a function check(k) to indicate whether the array can be turned into a zero array after the first k queries. We can use a difference array to maintain the value of each element.

Define an array d of length n + 1, initialized to all 0. For each of the first k queries [l, r, val], we add val to d[l] and subtract val from d[r + 1].

Then we iterate through the array d in the range [0, n - 1], accumulating the prefix sum s. If nums[i] > s, it means nums cannot be transformed into a zero array, so we return false.

During the binary search, if check(k) returns true, it means the array can be turned into a zero array, so we update the right boundary r to k; otherwise, we update the left boundary l to k + 1.

Finally, we check whether l > m. If so, return -1; otherwise, return l.

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

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n * m), where n is the length of nums and m is the number of queries. Each query may require iterating over the entire range of the array.
Space Complexity: O(1), since all modifications are done in place.

Difference Array Approach for Range Update

Time Complexity: O(n + m), where n is the length of nums and m is the number of queries, optimizing the brute-force complexity significantly.
Space Complexity: O(n), for the difference array storage.

Difference Array + Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SimulationO(n * m)O(1)Useful for understanding the mechanics of the queries or when constraints are very small.
Binary Search + Difference ArrayO((n + m) log m)O(n)Optimal solution for large inputs where many range updates must be processed efficiently.

Video Solution

Zero Array Transformation II | Brute Force | Better | Leetcode 3356 | codestorywithMIK • codestorywithMIK • 23,326 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Zero Array Transformation II easy or hard?
Zero Array Transformation II is considered a medium-level problem. The challenge comes from recognizing the monotonic property that enables binary search and using a difference array to handle range updates efficiently.
Zero Array Transformation II Python/Java solution
Most implementations use binary search and a difference array. The same logic translates easily across Python, Java, C++, and JavaScript because it only relies on array operations and prefix sum accumulation.
What is the best approach for Zero Array Transformation II?
The most efficient approach uses binary search combined with a difference array. Binary search finds the minimum number of queries required, while the difference array efficiently applies range decrements in O(1) per query. Each check runs in O(n + k) time, giving an overall complexity of O((n + m) log m).
Is Zero Array Transformation II asked at Google/Amazon/Meta?
Problems involving binary search with prefix sums and range updates are common in interviews at companies like Google, Amazon, and Meta. Variants that combine monotonic conditions with efficient range processing frequently appear in algorithm rounds.
What data structure is used in Zero Array Transformation II?
The main techniques are a difference array and prefix sums for efficient range updates, combined with binary search to find the minimum number of queries required.
What is the time complexity of Zero Array Transformation II?
The optimal solution runs in O((n + m) log m) time and O(n) space. Binary search is performed over the number of queries (m), and each feasibility check processes the first k queries using a difference array and a prefix sum scan.
How to solve Zero Array Transformation II in O((n + m) log m)?
Use binary search on the number of queries. For a candidate k, apply the first k range operations using a difference array. Build the prefix sum to compute total decrements at each index and verify that it is at least nums[i] for every position.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Corporate Flight Bookings

Next

Minimum Moves to Make Array Complementary