Problem Description

You are given an integer array nums of length n and a 2D array queries where each query is represented as queries[i] = [li, ri, vali].

For each query, you can perform the following action on nums:

• Choose any value between 0 and vali (inclusive) for each index in the range [li, ri]
• Subtract the chosen value from the element at that index
• The amount subtracted can be different for each index within the range

A Zero Array is defined as an array where all elements equal 0.

Your task is to find the minimum number k such that after processing the first k queries in sequence, you can transform nums into a Zero Array. If it's impossible to achieve a Zero Array using any number of the given queries, return -1.

For example, if you have nums = [3, 2, 1] and a query [0, 2, 2], you could:

• Subtract 2 from index 0 (3 becomes 1)
• Subtract 2 from index 1 (2 becomes 0)
• Subtract 1 from index 2 (1 becomes 0)

The key insight is that each query provides a "budget" of reductions you can apply flexibly across the specified range, and you need to determine how many queries (processed in order) are sufficient to reduce all elements to zero.

Intuition

The key observation is that this problem exhibits monotonic behavior: if we can transform the array into a Zero Array using the first k queries, then we can definitely do it with the first k+1 queries (or any number greater than k). This is because having more queries only gives us more "reduction power" - we never lose the ability to reduce elements.

This monotonicity immediately suggests binary search on the answer. Instead of checking every possible value of k from 1 to m (where m is the total number of queries), we can use binary search to efficiently find the minimum k.

For checking whether a specific number of queries k is sufficient, we need to determine the maximum reduction available at each index after applying the first k queries. Here's where the difference array technique becomes crucial:

• Each query [l, r, val] adds val units of reduction capacity to all indices in range [l, r]
• Multiple queries can overlap, so the total reduction capacity at each index is cumulative
• We can efficiently compute these cumulative values using a difference array

The difference array works by marking the start and end of each range:

• Add val at position l (start of range)
• Subtract val at position r+1 (just after end of range)
• When we compute the prefix sum, we get the actual reduction capacity at each position

For each index i, if nums[i] is greater than the total reduction capacity available at that index, then k queries are insufficient. Otherwise, we can strategically use the available reduction to bring nums[i] down to zero.

This approach transforms the problem from "how should we optimally apply each query" to "is the total reduction capacity at each index sufficient", which is much simpler to verify.

Learn more about Binary Search and Prefix Sum patterns.

Solution Approach

The solution implements binary search combined with a difference array to efficiently find the minimum number of queries needed.

Binary Search Setup: We use binary search to find the minimum k in the range [0, m] where m is the total number of queries. The bisect_left function searches for the first value where check(k) returns True.

The Check Function: The check(k) function determines if the first k queries provide enough reduction capacity to transform nums into a Zero Array.

1. Initialize Difference Array: Create an array d of length n + 1 filled with zeros. This will track the reduction capacity changes.

2. Process First k Queries: For each query [l, r, val] in the first k queries:

   • Add val to d[l] (marking the start of the range)
   • Subtract val from d[r + 1] (marking the end of the range)

3. Compute Actual Reduction Capacity:

   • Initialize a running sum s = 0
   • Iterate through each index i from 0 to n-1
   • Add d[i] to the running sum s
   • At each position, s represents the total reduction capacity available
   • If nums[i] > s, it means we cannot reduce nums[i] to zero with the available capacity, so return False

4. Return Result: If we successfully process all indices without finding any insufficiency, return True.

Final Answer: The binary search finds the leftmost position l where check(l) is True.

• If l > m, it means even using all queries isn't sufficient, so return -1
• Otherwise, return l as the minimum number of queries needed

Time Complexity: O(m * log(m) * n) where m is the number of queries and n is the length of nums. The binary search runs O(log m) iterations, and each check operation takes O(m + n) time.

Space Complexity: O(n) for the difference array.

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Given:

• nums = [3, 2, 1]
• queries = [[0, 1, 2], [1, 2, 1], [0, 2, 1]]

We need to find the minimum number of queries k such that we can transform nums into a Zero Array.

Step 1: Binary Search Setup We'll binary search on the range [0, 3] (since we have 3 queries total).

Step 2: Check if k=2 queries are sufficient

Let's check if the first 2 queries [[0, 1, 2], [1, 2, 1]] provide enough reduction capacity.

Building the Difference Array:

• Initialize: d = [0, 0, 0, 0] (length n+1 = 4)
• Query 1 [0, 1, 2]:
  • d[0] += 2 → d = [2, 0, 0, 0]
  • d[2] -= 2 → d = [2, 0, -2, 0]
• Query 2 [1, 2, 1]:
  • d[1] += 1 → d = [2, 1, -2, 0]
  • d[3] -= 1 → d = [2, 1, -2, -1]

Computing Reduction Capacity via Prefix Sum:

• Index 0: s = 0 + d[0] = 0 + 2 = 2
  • Check: nums[0] = 3 > 2? Yes! Cannot reduce 3 to 0 with only 2 units.
  • Return False

Since k=2 is insufficient, binary search will try a larger value.

Step 3: Check if k=3 queries are sufficient

Using all 3 queries [[0, 1, 2], [1, 2, 1], [0, 2, 1]]:

Building the Difference Array:

• Initialize: d = [0, 0, 0, 0]
• Query 1 [0, 1, 2]: d = [2, 0, -2, 0]
• Query 2 [1, 2, 1]: d = [2, 1, -2, -1]
• Query 3 [0, 2, 1]:
  • d[0] += 1 → d = [3, 1, -2, -1]
  • d[3] -= 1 → d = [3, 1, -2, -2]

Computing Reduction Capacity:

• Index 0: s = 0 + 3 = 3
  • Check: nums[0] = 3 ≤ 3? Yes! Can reduce to 0.
• Index 1: s = 3 + 1 = 4
  • Check: nums[1] = 2 ≤ 4? Yes! Can reduce to 0.
• Index 2: s = 4 + (-2) = 2
  • Check: nums[2] = 1 ≤ 2? Yes! Can reduce to 0.
• Return True

Step 4: Binary Search Conclusion The binary search finds that:

• k=2 is insufficient
• k=3 is sufficient

Therefore, the minimum k is 3.

Key Insight: The difference array elegantly tracks how reduction capacity accumulates across overlapping ranges. When we compute the prefix sum, we get the exact total reduction available at each position, making it easy to verify if we have enough "budget" to reduce each element to zero.

Solution Implementation

Time and Space Complexity

Time Complexity: O((n + m) × log m)

The algorithm uses binary search on the range [0, m] where m is the length of queries. Binary search performs O(log m) iterations.

For each binary search iteration, the check function is called, which:

• Iterates through k queries (at most m queries) to build the difference array: O(m)
• Iterates through nums array to verify the condition using the difference array: O(n)

Therefore, each check call takes O(n + m) time, and with O(log m) binary search iterations, the total time complexity is O((n + m) × log m).

Space Complexity: O(n)

The space complexity is determined by:

• The difference array d of size n + 1: O(n)
• Other variables like s, l, k use constant space: O(1)

The total space complexity is O(n), where n is the length of the nums array.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Misunderstanding Query Operations as Additions Instead of Subtractions

The problem states that queries allow you to subtract values from elements to reduce them to zero, but the solution code treats queries as additions. This is a critical conceptual error that would lead to completely incorrect results.

The Pitfall:

• The code adds value to the difference array: diff_array[left] += value
• Then checks if original_value > cumulative_sum
• This logic assumes we're adding to elements and checking if additions exceed original values

The Correct Understanding:

• Queries provide "reduction capacity" - they allow subtracting from elements
• We need to check if the total reduction capacity at each position is sufficient to reduce that element to zero

Solution:

def can_make_zero(num_queries: int) -> bool:
    # Track maximum reduction available at each position
    reduction_capacity = [0] * (len(nums) + 1)
  
    # Each query provides reduction capacity in its range
    for left, right, value in queries[:num_queries]:
        reduction_capacity[left] += value      # Start of reduction range
        reduction_capacity[right + 1] -= value  # End of reduction range
  
    # Check if reduction capacity is sufficient at each position
    current_capacity = 0
    for i, original_value in enumerate(nums):
        current_capacity += reduction_capacity[i]
        # Need enough capacity to reduce original value to zero
        if original_value > current_capacity:
            return False
  
    return True

2. Off-by-One Error in Binary Search Range

The Pitfall: Using bisect_left(range(total_queries + 1), ...) is correct, but developers often mistakenly use range(total_queries), forgetting that we might need all queries.

Why This Matters:

• If exactly total_queries queries are needed, range(total_queries) would miss this valid answer
• The search space should include the possibility of using 0 to total_queries queries (inclusive)

3. Incorrect Difference Array Boundary Handling

The Pitfall: Forgetting to allocate n + 1 elements for the difference array, or incorrectly handling the right + 1 index.

Common Mistake:

# Wrong: This would cause IndexError when right == n-1
diff_array = [0] * len(nums)  # Should be len(nums) + 1
diff_array[right + 1] -= value  # Would fail for last element

Correct Approach: Always allocate one extra element to safely handle the range end marker at right + 1.