aboutsummaryrefslogtreecommitdiff
path: root/zero_array_transformation1.py
blob: e4cc270b8753c3aa97d1b70c690a51085a168ed6 (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
# 3355. Zero Array Transformation I

"""
you are given an integer array 'nums' of length 'n' and a 2d array 'queries'
where 'queries[i] = [li, ri]'. for each 'queries[i]' select a subset of
indices within the range '[li, ri]' in 'nums' and decrement the values at the
selected indices by 1. a zero array is an array where all elements are equal
to 0. return true if it is possible to transform 'nums' into a zero array
after processing all the queries sequentially, otherwise return false.
"""


class Solution(object):
    def isZeroArray(self, nums, queries):
        """
        :type nums: List[int]
        :type queries: List[List[int]]
        :rtype: bool
        """
        n = len(nums)
        freq = [0] * (n + 1)
        for l, r in queries:
            freq[l] += 1
            freq[r + 1] -= 1
        cnt = 0
        for i, j in enumerate(nums):
            cnt += freq[i]
            if j > cnt:
                return False
        return True


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