3356.Zero_Array_Transformation_II(Medium).md

3356. Zero Array Transformation II (Medium)

Date and Time: Mar 13, 2025 (EST)

Link: https://leetcode.com/problems/zero-array-transformation-ii

Question:

You are given an integer array nums of length n and a 2D array queries where queries[i] = [l_i, r_i, val_i].

Each queries[i] represents the following action on nums:

• Decrement the value at each index in the range [l_i, r_i] in nums by at most val_i.

• 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.

Example 1:

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:

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<=\text{nums.length}<={10}^5$

• $0<=\text{nums[i]}<=5\ast {10}^5$

• $1<=\text{queries.length}<={10}^5$

• $\text{queries[i].length}==3$

• $0<=l_i<=r_i<\text{nums.length}$

• $1<=va{l}_i<=5$

Walk-through:

We use Binary Search on queries to find the minimum k we need that can make zero array.

We can check by building difference array, where for each query = [l, r, v], we update diff[l] += val, diff[r+1] -= val, only two positions can represent the whole range. Because we need to calculate prefixSum, so if we add val at the beginning left of the range, we can keep this val in prefixSum until right+1, that's why we need to subtract val at right+1 in the end.

Each time we update the prefixSum, we also need to compare it with nums[i] to make sure prefixSum >= nums[i] for every element in nums. Otherwise, we can return False.

Python Solution:

class Solution:
    def minZeroArray(self, nums: List[int], queries: List[List[int]]) -> int:
        # Build differenceArray, +val at left, -val at right+1
        # Calculate the prefixSum and compare with each nums[i]
        # Want all current prefixSum >= nums[i]
        # Then use Binary Search to find the correct k, update to search the left of current k

        # TC: O((n+m)log(m)), m=len(queries), SC: O(n)
        def buildArray(k):
            diff = [0] * (len(nums) + 1)
            # Update diff for difference array
            for i in range(k):
                l, r, v = queries[i]
                diff[l] += v
                diff[r+1] -= v
            # Compare if prefixSum >= each elem in nums
            prefixSum = 0
            for i in range(len(nums)):
                prefixSum += diff[i]
                if prefixSum < nums[i]:
                    return False
            return True
        
        # Run Binary Search to find the correct k
        l, r = 0, len(queries)
        ans = float("inf")
        while l <= r:
            m = (l+r) // 2
            # If we successfully find one, find m's left
            if buildArray(m):
                ans = m
                r = m - 1
            else:
                l = m + 1
        return -1 if ans == float("inf") else ans

Time Complexity: $O((n+m)log(m))$, n is len(nums), m is len(queries). We apply Binary Search on queries, and each time we need to search on nums and queries.
Space Complexity: $O(n)$, we create a difference array = len(nums)+1 each time.