LC-3355 Medium LeetCode

3355. Zero Array Transformation I

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 46% Topics: Array, Prefix Sum

Reading material

Arrays & Hashing 12 min Prefix Sums & Difference Arrays 11 min

Reference solution (spoiler · python)

# Time:  O(n + q)
# Space: O(n)

# line sweep
class Solution(object):
    def isZeroArray(self, nums, queries):
        """
        :type nums: List[int]
        :type queries: List[List[int]]
        :rtype: bool
        """
        events = [0]*(len(nums)+1)
        for l, r in queries:
            events[l] += 1
            events[r+1] -= 1
        curr = 0
        for i in xrange(len(nums)):
            curr += events[i]
            if nums[i] > curr:
                return False
        return True

Solution from kamyu104/LeetCode-Solutions · MIT