LC-2772 Medium LeetCode

2772. Apply Operations to Make All Array Elements Equal to Zero

Read the full problem statement on LeetCode.

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

Reading material

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

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

# greedy, sliding window
class Solution(object):
    def checkArray(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: bool
        """
        curr = 0
        for i, x in enumerate(nums):
            if x-curr < 0:
                return False
            nums[i] -= curr
            curr += nums[i]
            if i-(k-1) >= 0:
                curr -= nums[i-(k-1)]
        return curr == 0

Solution from kamyu104/LeetCode-Solutions · MIT