Apply Operations to Make All Array Elements Equal to Zero — LeetCode 2772 Python Solution

The problem

You are given a 0-indexed integer array nums and a positive integer k. You can apply the following operation on the array any number of times: Choose any subarray of size k from the array and decrease all its elements by 1.

Example

Input

nums = [2,2,3,1,1,0], k = 3

Output

true

Explanation

We can do the following operations:

Python solution

class Solution:
    def checkArray(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        d = [0] * (n + 1)
        s = 0
        for i, x in enumerate(nums):
            s += d[i]
            x += s
            if x == 0:
                continue
            if x < 0 or i + k > n:
                return False
            s -= x
            d[i + k] += x
        return True

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 2772. Apply Operations to Make All Array Elements Equal to Zero is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems