aboutsummaryrefslogtreecommitdiff
path: root/zero_array_transformation3.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-05-21 20:02:51 -0600
committerJack Sangdahl <[email protected]>2025-05-21 20:02:51 -0600
commit34314ef21ca6e4b6fbb812563c168d01aac36f09 (patch)
treedf4134857e71848c5d2a97c78f8fcd9c594dfe93 /zero_array_transformation3.py
parent99e31333a19757ce2a032fb90f694dfacd3cb80d (diff)
downloadleetcode-34314ef21ca6e4b6fbb812563c168d01aac36f09.tar.gz
leetcode-34314ef21ca6e4b6fbb812563c168d01aac36f09.zip
3362. zero array transformation 3
Diffstat (limited to 'zero_array_transformation3.py')
-rw-r--r--zero_array_transformation3.py41
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]]))