diff options
author | Jack Sangdahl <[email protected]> | 2025-05-21 20:02:51 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-05-21 20:02:51 -0600 |
commit | 34314ef21ca6e4b6fbb812563c168d01aac36f09 (patch) | |
tree | df4134857e71848c5d2a97c78f8fcd9c594dfe93 /zero_array_transformation3.py | |
parent | 99e31333a19757ce2a032fb90f694dfacd3cb80d (diff) | |
download | leetcode-34314ef21ca6e4b6fbb812563c168d01aac36f09.tar.gz leetcode-34314ef21ca6e4b6fbb812563c168d01aac36f09.zip |
3362. zero array transformation 3
Diffstat (limited to 'zero_array_transformation3.py')
-rw-r--r-- | zero_array_transformation3.py | 41 |
1 files changed, 41 insertions, 0 deletions
diff --git a/zero_array_transformation3.py b/zero_array_transformation3.py new file mode 100644 index 0000000..61ceb98 --- /dev/null +++ b/zero_array_transformation3.py @@ -0,0 +1,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]])) |