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

### [Problem link](https://leetcode.com/problems/apply-operations-to-make-all-array-elements-equal-to-zero/)

###### tags: `leedcode` `python` `medium` `Greedy` `Difference Array`

You are given a **0-indexed** integer array <code>nums</code> and a positive integer <code>k</code>.

You can apply the following operation on the array **any** number of times:

- Choose **any** subarray of size <code>k</code> from the array and **decrease** all its elements by <code>1</code>.

Return <code>true</code> if you can make all the array elements equal to <code>0</code>, or <code>false</code> otherwise.

A **subarray** is a contiguous non-empty part of an array.

**Example 1:**

Input: nums = [2,2,3,1,1,0], k = 3
Output: true
Explanation: We can do the following operations:
- Choose the subarray [2,2,3]. The resulting array will be nums = [1,1,2,1,1,0].
- Choose the subarray [2,1,1]. The resulting array will be nums = [1,1,1,0,0,0].
- Choose the subarray [1,1,1]. The resulting array will be nums = [0,0,0,0,0,0].

**Example 2:**

Input: nums = [1,3,1,1], k = 2
Output: false
Explanation: It is not possible to make all the array elements equal to 0.

**Constraints:**

- <code>1 <= k <= nums.length <= 10⁵</code>
- <code>0 <= nums[i] <= 10⁶</code>

## Solution 1 (TLE)

class Solution:
    def checkArray(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        arr = [0] * n

        for i in range(n - k + 1):
            if arr[i] > nums[i]:
                return False
            diff = nums[i] - arr[i]
            for j in range(i, i + k):
                arr[j] += diff

        for i in range(n - k + 1, n):
            if arr[i] != nums[i]:
                return False

        return True

## Solution 2 - Greedy & Difference Array (從nums往下扣)

class Solution:
    def checkArray(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        diff = [0] * (n + 1)

        # build difference array
        diff[0] = nums[0]
        for i in range(1, n):
            diff[i] = nums[i] - nums[i - 1]

        for i in range(n):
            delta = diff[i]
            if delta < 0:  # 如果<0代表nums[i]左側的數字太大, 沒救.
                return False
            if i + k < n + 1:
                diff[i] -= delta
                diff[i + k] += delta

        # diff[-2]才是代表nums[-1], 如果diff[-2] == 0, 則代表 
        # 有辦法讓nums的所有數字皆為0.
        return diff[-2] == 0

## Solution 3 - Greedy & Difference Array (從0往上加)

class Solution:
    def checkArray(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        diff = [0] * (n + 1)
        
        cur = 0
        for i in range(n):
            cur += diff[i]
            if cur > nums[i]:
                return False
            delta = nums[i] - cur
            if delta > 0 and i + k < n + 1:
                diff[i] += delta
                diff[i + k] -= delta
            cur += delta

        return cur + diff[-1] == 0

>### Complexity
>n = nums.length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O($n^2$) | O(n) |
>| Solution 1 | O(n) | O(n) |
>| Solution 1 | O(n) | O(n) |

## Note
[官神yt](https://youtu.be/7R7-4eIjWqM)

有點greedy的想法, 從左往右一個一個檢查, 想辦法讓當前檢查的數字為0
ex: nums = [2, 4, 3, 1], k = 2
=> nums = [0, 2, 3, 1]
=> nums = [0, 0, 1, 1]
=> nums = [0, 0, 0, 0]

但是這樣從左到右遍歷一次, 假設n = 10000, k = 100, 會做(n - k)*k次減法, 這樣會超時.

所以就出現了不用每次都要慢慢做k次減法的方法--Difference array.
[difference array介紹](https://zhuanlan.zhihu.com/p/301509170)

建議不懂difference array的話先看一下介紹, 不然會跟我一樣聽不懂官神的解說.