We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Zero Array Transformation II

Number: 3643

Difficulty: Medium

Paid? No

Companies: Google, Meta, Amazon, Bloomberg

Problem Description

Given an integer array nums and a list of queries where each query is represented as [l, r, val], you can subtract from each element in the subarray nums[l]…nums[r] an independently chosen amount up to val. The goal is to determine the minimum number of queries (taking them in sequence) needed such that it becomes possible to reduce every element in nums to 0 (i.e. obtain a Zero Array). If no sequence of queries can achieve this, return -1.

Key Insights

  • Each query [l, r, val] offers an independent budget: for every index i in [l, r], you can reduce nums[i] by any amount up to val.
  • The total reduction available at an index i after processing some queries is the sum of all val’s from queries that cover index i.
  • To be able to zero out nums[i], this sum must be at least nums[i].
  • The problem reduces to finding the smallest k (the number of queries from the beginning) such that for every index i, the cumulative available decrement (sum of val’s from the first k queries covering i) is at least nums[i].
  • A binary search on the number of queries k is a natural strategy, with a "feasibility check" using a difference array (prefix sum technique) to quickly compute the cumulative decrement available for each index.

Space and Time Complexity

Time Complexity: O((n + Q) * log Q), where n is the length of the nums array and Q is the number of queries.
Space Complexity: O(n), for storing the difference array and cumulative sums.

Solution

We use a binary search over the number of queries k. For each candidate k:

  1. Build a difference array of length (n+1) and update it for the first k queries. For every query [l, r, val], we add val at diff[l] and subtract val at diff[r+1] (if within bounds).
  2. Compute the prefix sum on the difference array to obtain the total decrement available at each index.
  3. Check if for every index the available decrement is at least nums[i]. If yes, candidate k is feasible.
  4. Return the minimum feasible k found via binary search or -1 if none exists.

This approach leverages the independence of query decrements and the fact that queries are applied in order.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with line-by-line comments.

# Python solution for Zero Array Transformation II

def can_transform(nums, queries, k):
    n = len(nums)
    # Initialize difference array for range updates
    diff = [0] * (n + 1)
    
    # Process the first k queries and update the difference array
    for i in range(k):
        l, r, val = queries[i]
        diff[l] += val
        if r + 1 < n:
            diff[r + 1] -= val
    
    # Convert difference array to prefix sum for available decrement at each index
    available = 0
    for i in range(n):
        available += diff[i]
        # If the available decrement is less than the required decrement, transformation fails.
        if available < nums[i]:
            return False
    return True

def min_queries_to_zero(nums, queries):
    # If nums is already a Zero Array, answer is 0.
    if all(num == 0 for num in nums):
        return 0

    left, right = 0, len(queries) + 1  # right is exclusive upper bound
    while left < right:
        mid = (left + right) // 2
        if can_transform(nums, queries, mid):
            right = mid
        else:
            left = mid + 1
    
    # If left is beyond the number of queries, transformation is impossible.
    return left if left <= len(queries) else -1

# Example usage:
nums = [2, 0, 2]
queries = [[0, 2, 1], [0, 2, 1], [1, 1, 3]]
print(min_queries_to_zero(nums, queries))  # Expected output: 2
← Back to All Questions