aboutsummaryrefslogtreecommitdiff
path: root/zero_array_transformation3.py
blob: 61ceb98b69e6d4971dd7bbaefa7a3f558ab393e3 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 3362. Zero Array Transformation III
from sortedcontainers import SortedList

"""
you are given an integer array 'nums' of length 'n' and a 2d array 'queries'
where 'queries[i] = [li, ri]'. each 'queries[i]' represents the following
action on 'nums': decrement the value at each index in the range '[li, ri]'
in 'nums' by at most 1. the amount by which the 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 maximum number of elements that can be
removed from 'queries' such that 'nums' can still be converted to a zero
array using the remaining queries. if it is not possible to convert 'nums' to
a zero array, return -1.
"""


class Solution(object):
    def maxRemoval(self, nums, queries):
        """
        :type nums: List[int]
        :type queries: List[List[int]]
        :rtype: int
        """
        queries = sorted(queries)[::-1]
        end, curr = SortedList(), SortedList()
        for i in range(len(nums)):
            while queries and queries[-1][0] <= i:
                end.add(queries.pop()[1])
            while curr and curr[0] < i:
                curr.pop(0)
            while nums[i] > len(curr):
                if not end or end[-1] < i:
                    return -1
                curr.add(end.pop())
        return len(end)


if __name__ == "__main__":
    obj = Solution()
    print(obj.maxRemoval(nums=[2, 0, 2], queries=[[0, 2], [0, 2], [1, 1]]))
    print(obj.maxRemoval(nums=[1, 1, 1, 1], queries=[[1, 3], [0, 2], [1, 3], [1, 2]]))