Today’s problem

https://leetcode.com/problems/zero-array-transformation-iii/

Intuition

This question requires us to find the number of sections that is “useful”, or in other words, the smallest number of sections that is enough to make the array a zero array.

The key to solve this question is to change a view of how we look at this problem: if we take each element in the array seperately, then we can use greedy algorithm to solve this problem.

The thing is, if we look at each element seperately, i.e., to make the entire array a zero array, we must make each element zero.

In this case, for each element, the best way is to find a section that contains this elemnt, while it has a further tail. This is because a furtuer tail means to cover more elements in the future, which will be always better compared with the sections that has a shorter tail.

Therefore, now we need a data structure to store the current “farest tail”. This data structure need to add element dynamically and delete the largest item, when a heap will be the best way to store the “tail”.

Approach

Therefore, we can form our algorithm.

1. First, we need to sort the array using the left end of the query as keyword. In this case, we can find which queries has a left end that is to the left of our current index.
2. Then we need to create a difference array to deal with the section add operation; a heap to store the right end of the queries; and an index to show where we are currently at when we traverse all the queries.
3. The next step is to traverse the number array: for each element in the number array, we first need to push all the queries that has the left end that is less the current index. This makes all the elements in the heap potentially available to use to decrease the current element.
4. Then we will deal with the current element, finding all the available queries for the current element, then deal with the section decrease operation. (In this case, we ensure every operation is valid by checking that the endpoint of the heap top is larger or equal to the index, so that the left end of the array will be less or equal to the current index, and the right end of the array will be larger or equal to the current index. Therefore, we guarentee that the operation is valid).
5. Finally, if the number is still larger than 0, we will return -1; otherwise, we will return the remaining element in h, which is all the unused elements.

Complexity

• Time complexity:

$O(N \times log(m))$

• Space complexity:

$O(N + M)$

Code

class Solution:
    def maxRemoval(self, nums: List[int], queries: List[List[int]]) -> int:
        queries.sort(key = lambda x: x[0])
        diff = [0] * (len(nums) + 1)
        h = []
        idx, now = 0,0

        for i in range(len(nums)):
            while idx < len(queries) and queries[idx][0] <= i:
                heappush(h, -queries[idx][1])
                idx += 1
            
            now += diff[i]

            while h and now < nums[i] and -h[0] >= i:
                now += 1
                diff[-heappop(h) + 1] -= 1

            if now < nums[i]:
                return -1
            
        return len(h)

For more solutions, please visit My blog