3356. Zero Array Transformation II - Solution

The problem

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

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

Decrement the value at each index in the range [l_i, r_i] in nums by at most val_i.
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 <= 10⁵
0 <= nums[i] <= 5 * 10⁵
1 <= queries.length <= 10⁵
queries[i].length == 3
0 <= l_i <= r_i < nums.length
1 <= val_i <= 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.

Python

def minQueries(nums, queries):
    for k in range(len(queries)):
        l, r, val = queries[k]
        for i in range(l, r+1):
            nums[i] = max(0, nums[i] - val)
        if all(x == 0 for x in nums):
            return k + 1
    return -1

nums = [2, 0, 2]
queries = [[0, 2, 1], [0, 2, 1], [1, 1, 3]]
print(minQueries(nums, queries))

Java

import java.util.Arrays;

public class ZeroArrayTransformation {
    public static int minQueries(int[] nums, int[][] queries) {
        for (int k = 0; k < queries.length; k++) {
            int l = queries[k][0], r = queries[k][1], val = queries[k][2];
            for (int i = l; i <= r; i++) {
                nums[i] = Math.max(0, nums[i] - val);
            }
            boolean isZero = true;
            for (int num : nums) {
                if (num != 0) {
                    isZero = false;
                    break;
                }
            }
            if (isZero) return k + 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {2, 0, 2};
        int[][] queries = {{0, 2, 1}, {0, 2, 1}, {1, 1, 3}};
        System.out.println(minQueries(nums, queries));
    }
}

C++

#include <vector>
#include <algorithm>
using namespace std;

int minQueries(vector<int>& nums, vector<vector<int>>& queries) {
    for (int i = 0; i < queries.size(); i++) {
        int l = queries[i][0];
        int r = queries[i][1]; 
        int val = queries[i][2];
        for (int j = l; j <= r; j++) {
            nums[j] = max(0, nums[j] - val);
        }
        if (all_of(nums.begin(), nums.end(), [](int x) { return x == 0; })) return i + 1;
    }
    return -1;
}

int main() {
    vector<int> nums = {2, 0, 2};
    vector<vector<int>> queries = {{0, 2, 1}, {0, 2, 1}, {1, 1, 3}};
    int result = minQueries(nums, queries);
    return result;
}

JavaScript

function minQueries(nums, queries) {
    for (let k = 0; k < queries.length; k++) {
        const [l, r, val] = queries[k];
        for (let i = l; i <= r; i++) {
            nums[i] = Math.max(0, nums[i] - val);
        }
        if (nums.every(num => num === 0)) {
            return k + 1;
        }
    }
    return -1;
}

const nums = [2, 0, 2];
const queries = [[0, 2, 1], [0, 2, 1], [1, 1, 3]];
console.log(minQueries(nums, queries));

#include <stdio.h>

int minQueries(int* nums, int numsSize, int queries[][3], int queriesSize) {
    for (int i = 0; i < queriesSize; i++) {
        int l = queries[i][0];
        int r = queries[i][1]; 
        int val = queries[i][2];
        for (int j = l; j <= r; j++) {
            nums[j] = (nums[j] >= val) ? (nums[j] - val) : 0;
        }
        int allZero = 1;
        for (int j = 0; j < numsSize; j++) {
            if (nums[j] != 0) {
                allZero = 0;
                break;
            }
        }
        if (allZero) return i + 1;
    }
    return -1;
}

int main() {
    int nums[] = {2, 0, 2};
    int queries[][3] = {{0, 2, 1}, {0, 2, 1}, {1, 1, 3}};
    int result = minQueries(nums, sizeof(nums) / sizeof(nums[0]), queries, sizeof(queries) / sizeof(queries[0]));
    printf("%d\n", result);
    return 0;
}

using System;
using System.Linq;

public class ZeroArrayTransformation {
    public static int MinQueries(int[] nums, int[][] queries) {
        for (int k = 0; k < queries.Length; k++) {
            int l = queries[k][0], r = queries[k][1], val = queries[k][2];
            for (int i = l; i <= r; i++) {
                nums[i] = Math.Max(0, nums[i] - val);
            }
            if (nums.All(x => x == 0)) return k + 1;
        }
        return -1;
    }

    public static void Main() {
        int[] nums = {2, 0, 2};
        int[][] queries = { new[] {0, 2, 1}, new[] {0, 2, 1}, new[] {1, 1, 3} };
        Console.WriteLine(MinQueries(nums, queries));
    }
}

The Python implementation follows the same brute force approach, iterating over queries and applying the decrement operation range-wise. The use of Python's built-in all function makes the check for the Zero Array concise and clear, enhancing readability.

Complexity

Time Complexity: O(n * m). Space Complexity: O(1).

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.

Python

def minQueries(nums, queries):
    diff = [0] * (len(nums) + 1)
    
    for k, (l, r, val) in enumerate(queries):
        diff[l] -= val
        if r + 1 < len(nums):
            diff[r + 1] += val

        current = 0
        isZero = True
        for i in range(len(nums)):
            current += diff[i]
            if nums[i] + current > 0:
                isZero = False
                break
        if isZero:
            return k + 1

    return -1

nums = [2, 0, 2]
queries = [[0, 2, 1], [0, 2, 1], [1, 1, 3]]
print(minQueries(nums, queries))

Java

public class ZeroArrayTransformation {
    public static int minQueries(int[] nums, int[][] queries) {
        int[] diff = new int[nums.length + 1];
        
        for (int k = 0; k < queries.length; k++) {
            int l = queries[k][0], r = queries[k][1], val = queries[k][2];
            diff[l] -= val;
            if (r + 1 < nums.length) {
                diff[r + 1] += val;
            }

            int current = 0;
            boolean isZero = true;
            for (int i = 0; i < nums.length; i++) {
                current += diff[i];
                if (nums[i] + current > 0) {
                    isZero = false;
                    break;
                }
            }
            if (isZero) return k + 1;
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {2, 0, 2};
        int[][] queries = {{0, 2, 1}, {0, 2, 1}, {1, 1, 3}};
        System.out.println(minQueries(nums, queries));
    }
}

C++

#include <vector>
#include <iostream>
#include <cstring>
using namespace std;

int minQueries(vector<int>& nums, vector<vector<int>>& queries) {
    vector<int> diff(nums.size() + 1, 0);
    
    for (int i = 0; i < queries.size(); i++) {
        int l = queries[i][0];
        int r = queries[i][1];
        int val = queries[i][2];
        diff[l] -= val;
        if (r + 1 < nums.size())
            diff[r + 1] += val;

        int current = 0;
        bool allZero = true;
        for (int j = 0; j < nums.size(); j++) {
            current += diff[j];
            if (nums[j] + current > 0) {
                allZero = false;
                break;
            }
        }
        if (allZero) return i + 1;
    }
    return -1;
}

int main() {
    vector<int> nums = {2, 0, 2};
    vector<vector<int>> queries = {{0, 2, 1}, {0, 2, 1}, {1, 1, 3}};
    cout << minQueries(nums, queries) << endl;
    return 0;
}

JavaScript

function minQueries(nums, queries) {
    const diff = new Array(nums.length + 1).fill(0);
    
    for (let k = 0; k < queries.length; k++) {
        const [l, r, val] = queries[k];
        diff[l] -= val;
        if (r + 1 < nums.length) {
            diff[r + 1] += val;
        }

        let current = 0;
        let isZero = true;
        for (let i = 0; i < nums.length; i++) {
            current += diff[i];
            if (nums[i] + current > 0) {
                isZero = false;
                break;
            }
        }
        if (isZero) return k + 1;
    }
    return -1;
}

const nums = [2, 0, 2];
const queries = [[0, 2, 1], [0, 2, 1], [1, 1, 3]];
console.log(minQueries(nums, queries));

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

int minQueries(int* nums, int numsSize, int queries[][3], int queriesSize) {
    int diff[numsSize+1];
    memset(diff, 0, sizeof(diff));
    
    for (int i = 0; i < queriesSize; i++) {
        int l = queries[i][0];
        int r = queries[i][1];
        int val = queries[i][2];
        diff[l] -= val;
        if (r+1 < numsSize) diff[r+1] += val;

        int current = 0, allZero = 1;
        for (int j = 0; j < numsSize; j++) {
            current += diff[j];
            if ((nums[j] + current) > 0) {
                allZero = 0;
                break;
            }
        }
        if (allZero) return i + 1;
    }

    return -1;
}

int main() {
    int nums[] = {2, 0, 2};
    int queries[][3] = {{0, 2, 1}, {0, 2, 1}, {1, 1, 3}};
    int result = minQueries(nums, sizeof(nums) / sizeof(nums[0]), queries, sizeof(queries) / sizeof(queries[0]));
    printf("%d\n", result);
    return 0;
}

using System;
using System.Linq;

public class ZeroArrayTransformation {
    public static int MinQueries(int[] nums, int[][] queries) {
        int[] diff = new int[nums.Length + 1];
        
        for (int k = 0; k < queries.Length; k++) {
            int l = queries[k][0], r = queries[k][1], val = queries[k][2];
            diff[l] -= val;
            if (r + 1 < nums.Length) {
                diff[r + 1] += val;
            }

            int current = 0;
            bool isZero = true;
            for (int i = 0; i < nums.Length; i++) {
                current += diff[i];
                if (nums[i] + current > 0) {
                    isZero = false;
                    break;
                }
            }
            if (isZero) return k + 1;
        }

        return -1;
    }

    public static void Main() {
        int[] nums = {2, 0, 2};
        int[][] queries = { new[] {0, 2, 1}, new[] {0, 2, 1}, new[] {1, 1, 3} };
        Console.WriteLine(MinQueries(nums, queries));
    }
}

Python implementation uses an efficient differential update mechanism which takes advantage of Python's list operations for clear and concise code. The difference array ensures only needed updates apply to affected indices.

Complexity

Time Complexity: O(n + m). Space Complexity: O(n).

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.

TypeScript

function minZeroArray(nums: number[], queries: number[][]): number {
    const [n, m] = [nums.length, queries.length];
    const d: number[] = Array(n + 1);
    let [l, r] = [0, m + 1];
    const check = (k: number): boolean => {
        d.fill(0);
        for (let i = 0; i < k; ++i) {
            const [l, r, val] = queries[i];
            d[l] += val;
            d[r + 1] -= val;
        }
        for (let i = 0, s = 0; i < n; ++i) {
            s += d[i];
            if (nums[i] > s) {
                return false;
            }
        }
        return true;
    };
    while (l < r) {
        const mid = (l + r) >> 1;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l > m ? -1 : l;
}

func minZeroArray(nums []int, queries [][]int) int {
	n, m := len(nums), len(queries)
	l := sort.Search(m+1, func(k int) bool {
		d := make([]int, n+1)
		for _, q := range queries[:k] {
			l, r, val := q[0], q[1], q[2]
			d[l] += val
			d[r+1] -= val
		}
		s := 0
		for i, x := range nums {
			s += d[i]
			if x > s {
				return false
			}
		}
		return true
	})
	if l > m {
		return -1
	}
	return l
}

Rust

impl Solution {
    pub fn min_zero_array(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> i32 {
        let n = nums.len();
        let m = queries.len();
        let mut d: Vec<i64> = vec![0; n + 1];
        let (mut l, mut r) = (0_usize, m + 1);

        let check = |k: usize, d: &mut Vec<i64>| -> bool {
            d.fill(0);
            for i in 0..k {
                let (l, r, val) = (
                    queries[i][0] as usize,
                    queries[i][1] as usize,
                    queries[i][2] as i64,
                );
                d[l] += val;
                d[r + 1] -= val;
            }
            let mut s: i64 = 0;
            for i in 0..n {
                s += d[i];
                if nums[i] as i64 > s {
                    return false;
                }
            }
            true
        };

        while l < r {
            let mid = (l + r) >> 1;
            if check(mid, &mut d) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if l > m { -1 } else { l as i32 }
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Brute Force Approach	Time Complexity: O(n * m). Space Complexity: O(1).
Difference Array Approach for Range Update	Time Complexity: O(n + m). Space Complexity: O(n).
Difference Array + Binary Search	–

Complexity analysis

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

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.

Zero Array Transformation II solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Difference Array Approach for Range Update

Approach 3: Difference Array + Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Zero Array Transformation II solution and explanation

The problem

Approach overview

Approach 1: Brute Force Approach

Approach 2: Difference Array Approach for Range Update

Approach 3: Difference Array + Binary Search

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems