Problem

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.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


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

Similar Problem

Zero Array Transformation 1 Zero Array Transformation 3

Solution

Method 1 - Binary Search with Range Updates Using Difference Array

The problem requires determining the minimum number of queries needed to transform the array nums into a Zero Array (all elements 0). Each query allows decrementing values in a range [li, ri] by at most vali. A direct approach of applying queries sequentially for every possible number k is inefficient, so we use binary search to efficiently determine the smallest k that works. To quickly process the range updates for each query, a difference array is used to simulate the effects.

Approach

  1. Treat the problem as finding the smallest k (minimum number of queries), and use binary search over k.
  2. For every k, check whether the first k queries can reduce nums to a Zero Array:
    • Use a difference array to efficiently apply the range updates defined by the first k queries.
    • Simulate the cumulative effects of the difference array on nums and verify if all elements become ≤ 0.
  3. If nums can be zeroed with k queries, explore smaller values of k (move left in binary search). Otherwise, move right to try larger k.
  4. Return the smallest valid k, or -1 if no such k exists.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Solution {
    public int minZeroArray(int[] nums, int[][] queries) {
        // Binary search for the minimum number of queries needed
        int left = 0, right = queries.length, ans = -1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            // Use a copy of nums to avoid modifying the original array
            int[] numsCopy = nums.clone();
            
            if (canZero(numsCopy, queries, mid)) {
                ans = mid;  // If possible with 'mid' queries, record and try for fewer queries
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        return ans;
    }

    // Helper function to check if nums can be reduced to a Zero Array with the first 'k' queries
    private boolean canZero(int[] nums, int[][] queries, int k) {
        int n = nums.length;
        int[] diff = new int[n + 1];  // Difference array for efficient range updates

        // Apply the first 'k' queries
        for (int i = 0; i < k; i++) {
            int li = queries[i][0];
            int ri = queries[i][1];
            int vali = queries[i][2];
            diff[li] -= vali; // Start decrement at index 'li'
            if (ri + 1 < n) {
                diff[ri + 1] += vali; // Stop decrement after index 'ri'
            }
        }

        // Simulate the effect of the difference array on nums
        int runningSum = 0;
        for (int i = 0; i < n; i++) {
            runningSum += diff[i];
            nums[i] += runningSum;
            if (nums[i] > 0) {
                return false;  // If any value remains positive, nums cannot be a Zero Array
            }
        }

        return true;  // All elements are ≤ 0, meaning nums is a Zero Array
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution:
    def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:
        def can_zero(nums: List[int], k: int) -> bool:
            n = len(nums)
            diff = [0] * (n + 1)  # Difference array for efficient range updates
            
            # Apply the first 'k' queries
            for i in range(k):
                li, ri, val = queries[i]
                diff[li] -= val  # Start decrement at index 'li'
                if ri + 1 < n:
                    diff[ri + 1] += val  # Stop decrement after index 'ri'
            
            # Simulate the effect on nums
            running_sum = 0
            for i in range(n):
                running_sum += diff[i]
                nums[i] += running_sum
                if nums[i] > 0:
                    return False  # nums cannot be zeroed if any value is positive
            
            return True  # All elements are ≤ 0, nums is a Zero Array

        # Binary search for the minimum 'k'
        left, right = 0, len(queries)
        ans = -1

        while left <= right:
            mid = (left + right) // 2
            
            # Use a copy of nums to avoid modifying the original
            nums_copy = nums[:]
            
            if can_zero(nums_copy, mid):
                ans = mid  # If it's possible with 'mid' queries
                right = mid - 1
            else:
                left = mid + 1

        return ans

Complexity

  • ⏰ Time complexity:  O(log(q) * (n + q)), where n is length of nums, q is number of queries
    • Binary Search: O(log(q)), as we’re searching over the number of queries.
    • Simulation for each k in Binary Search:
      • Building the difference array: O(k) for processing the first k queries.
      • Applying the difference array to nums: O(n) for updating values in the array.
      • Total per binary search iteration: O(n + k).
  • 🧺 Space complexity: O(n)
    • Difference Array: O(n), required to store range updates.
    • Cloned nums Array: O(n), used in simulations for each binary search iteration.