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

link

Dataset is 10^5, we can easily use 2 for loop to solve the question. the time complexity will be O(n^2)

We can use sweepline method to reduce O(n^2) to O(n)

class Solution:
    def checkArray(self, nums: List[int], k: int) -> bool:

        n = len(nums)


        M = defaultdict(int)

        current = 0

        for i in range(n):
            current += M.get(i, 0)

            if i + k <= n and nums[i] + current > 0:
                diff = nums[i] + current
                current -= diff
                M[i+k] += diff
            
            if nums[i] + current != 0:
                return False
        
        return True