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 III

Number: 3647

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

You are given an integer array nums of length n and a 2D array queries, where each query is represented as [l, r]. Each query allows you to decrement by at most 1 each number in nums between indices l and r (the amount you decrement at each index can be chosen independently). A “zero array” is an array in which every element is 0. The task is to remove as many queries as possible (i.e. maximize the count of removed queries) so that using the remaining queries it is still possible to convert nums to a zero array. If even using all queries it is impossible to convert nums to a zero array, return -1.

Key Insights

  • To convert nums to a zero array, each index i with value nums[i] must be covered (i.e. decremented) at least nums[i] times.
  • Each query (interval) gives exactly 1 decrement “credit” for every index in its range.
  • The problem is equivalent to selecting a minimum subset of queries such that for every index i the coverage (the count of chosen queries that cover i) is at least nums[i].
  • The maximum number of queries that can be removed equals total queries minus the minimum number of queries needed.
  • A greedy strategy works by sweeping from left to right and, at each index, if current coverage is insufficient, using available queries (those whose l is ≤ current index) that extend farthest to cover as many future indices as possible.

Space and Time Complexity

Time Complexity: O(n log m) where n is the length of nums and m is the number of queries (each query is pushed/popped from a heap). Space Complexity: O(n + m) due to the auxiliary arrays and heap.

Solution

We transform the problem into one of “multipoint covering” on a line. Every index i requires nums[i] “coverage”. We process indices left-to-right while maintaining a difference array (or running sum) of already added decrements from chosen queries. For every index i, if the current coverage (i.e. decrements applied) is less than nums[i], we have a shortage and must “select” additional queries. The selection is done greedily: among the queries that start at or before i, we choose the one that extends farthest right – so it covers not only position i but also as many future positions as possible. Each selected query adds 1 unit of coverage to all positions from its start index to its end index. We simulate this by updating a difference array so that when moving to the next index, we know the cumulative extra decrements provided by previously selected queries. If at any index the shortage cannot be resolved (i.e. no query covering i is available), the answer is -1. Otherwise, the answer is total queries minus the count of queries selected.

The algorithm uses:

  • A greedy sweep-line strategy.
  • A max-heap (or priority queue) keyed by the right endpoint of queries.
  • A difference array to perform range updates in O(1) time.

Code Solutions

import heapq

def maxQueriesRemoved(nums, queries):
    n = len(nums)
    total_queries = len(queries)
    # diff array to simulate range updates from selected queries
    diff = [0] * (n + 1)
    current_extra = 0  # current cumulative extra coverage at the current index
    chosen = 0  # count of selected queries

    # Sort queries by their start index
    queries_sorted = sorted(queries, key=lambda x: x[0])
    heap = []  # max-heap simulated using negatives (stores right endpoints)
    j = 0  # pointer to iterate queries_sorted

    for i in range(n):
        if i > 0:
            current_extra += diff[i]  # update current_extra based on diff array

        # Add all queries with start index <= i to the heap.
        while j < len(queries_sorted) and queries_sorted[j][0] <= i:
            # Push negative right endpoint to simulate max-heap.
            heapq.heappush(heap, -queries_sorted[j][1])
            j += 1

        # Determine how many more decrements are needed at index i.
        required = nums[i] - current_extra
        while required > 0:
            # Remove queries from the heap that do not cover i.
            while heap and -heap[0] < i:
                heapq.heappop(heap)
            if not heap:
                return -1  # not enough queries to cover the shortage at index i
            best_r = -heapq.heappop(heap)  # choose the query that extends farthest right
            chosen += 1
            # Apply the effect of this query using the difference array.
            diff[i] += 1
            if best_r + 1 < len(diff):
                diff[best_r + 1] -= 1
            current_extra += 1  # immediate effect at index i
            required -= 1

    return total_queries - chosen

# Example usage:
nums = [2, 0, 2]
queries = [[0, 2], [0, 2], [1, 1]]
print(maxQueriesRemoved(nums, queries))  # Output: 1
← Back to All Questions