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 I

Number: 3639

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given an array of nonnegative integers nums and a list of queries (each a pair [l, r]), we may “choose” a subset of indices in the given range for each query and decrement those chosen indices by 1. The question asks whether it is possible to transform nums into a Zero Array (all elements are 0) after processing the queries sequentially.

Key Insights

  • Each query allows you to decrement any subset of indices in the given range.
  • An index j can be decremented at most once by every query whose range covers it.
  • For an index j with value nums[j], it is necessary (and in this setting, sufficient) that there are at least nums[j] queries covering j.
  • A difference array (or prefix sum) can be used to efficiently compute the number of queries that cover each index.

Space and Time Complexity

Time Complexity: O(n + q) where n is the number of elements in nums and q is the number of queries. Space Complexity: O(n) for storing the coverage count.

Solution

We can solve this problem by first figuring out how many queries cover each index in nums. To do so, we use a difference array: for each query [l, r], we increment the count at index l and decrement the count just past r (if within bounds). A prefix sum of this difference array provides the coverage for every index. Then, for each index j, we simply check whether nums[j] is less than or equal to the number of queries covering that index. If for any index the required number exceeds the available queries, it is impossible to reduce nums[j] to 0 because each query can subtract at most 1 from that index. Otherwise, if every index meets its quota, the transformation is possible.

The main trick is to realize that since each query can independently choose any indices inside its range, the only real restriction is that each index must appear in at least as many queries as the number of decrements it needs.

Code Solutions

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

# Python solution for Zero Array Transformation I
def canTransformToZero(nums, queries):
    n = len(nums)
    # Initialize a difference array with 0's (size n+1 to handle r+1 decrement)
    diff = [0] * (n + 1)

    # Process each query to update the difference array
    for l, r in queries:
        diff[l] += 1
        if r + 1 < n:
            diff[r + 1] -= 1

    # Build the coverage count array using prefix sum
    coverage = [0] * n
    current = 0
    for i in range(n):
        current += diff[i]
        coverage[i] = current

    # Check each index: nums[i] must be <= coverage[i]
    for i in range(n):
        if nums[i] > coverage[i]:
            return False
    return True

# Example usage:
nums1 = [1,0,1]
queries1 = [[0,2]]
print(canTransformToZero(nums1, queries1))  # Expected True

nums2 = [4,3,2,1]
queries2 = [[1,3],[0,2]]
print(canTransformToZero(nums2, queries2))  # Expected False
← Back to All Questions