# Apply Operations to Make All Array Elements Equal to Zero
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/apply-operations-to-make-all-array-elements-equal-to-zero)
Canonical: https://scaleengineer.com/dsa/problems/apply-operations-to-make-all-array-elements-equal-to-zero
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array
---
## 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`.

Return `true` _if you can make all the array elements equal to_ `0`_, or_ `false` _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:**

* `1 <= k <= nums.length <= 105`
* `0 <= nums[i] <= 106`

# Approaches
## Naive Simulation
This approach directly simulates the process based on a greedy strategy. We iterate through the array from left to right. For each element `nums[i]`, we must make it zero. Since we have already processed elements `nums[0...i-1]`, we cannot apply any operation that affects them. The only way to reduce `nums[i]` without changing previous elements is by applying operations on subarrays starting at index `i`. Therefore, we must apply the decrement operation exactly `nums[i]` times on the subarray `nums[i...i+k-1]`. We repeat this for every element in the array.
**Time:** O(n * k), where n is the length of `nums`. The outer loop runs `n` times, and for each positive element, the inner loop runs `k` times. · **Space:** O(1) as we modify the array in-place and use a constant amount of extra space.
**Pros:** Simple to understand and implement.; It's a direct translation of the greedy logic.
**Cons:** Inefficient for large `n` and `k` due to its O(n*k) time complexity, which will time out on larger constraints.
### Explanation
The algorithm iterates through the array `nums` from left to right. At each index `i`, it ensures the element `nums[i]` becomes zero. If `nums[i]` is already zero, we move on. If `nums[i]` is positive, we must perform `nums[i]` decrement operations. To avoid altering the already-zeroed elements before `i`, these operations must apply to a subarray starting at `i`. This is only possible if a subarray of size `k` fits within the array bounds (i.e., `i + k <= n`). If `nums[i]` is positive but such an operation is not possible, we cannot make it zero, so we return `false`. Otherwise, we subtract `nums[i]` from all elements in the subarray `nums[i...i+k-1]`. If at any point an element becomes negative, it's an impossible scenario, and we return `false`. After iterating through the entire array, if we have successfully made `nums[0...n-2]` zero, the final answer depends on whether `nums[n-1]` has also become zero.

```java
class Solution {
    public boolean checkArray(int[] nums, int k) {
        // With k=1, we can decrement any element individually.
        // Since all nums[i] >= 0, we can always make them 0.
        if (k == 1) {
            return true;
        }
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] < 0) {
                return false;
            }
            if (nums[i] == 0) {
                continue;
            }
            // If nums[i] > 0, we must perform operations.
            // This is impossible if the subarray goes out of bounds.
            if (i + k > n) {
                return false;
            }
            int ops = nums[i];
            for (int j = i; j < i + k; j++) {
                nums[j] -= ops;
            }
        }
        // If we successfully processed all elements, the last one must be 0.
        return nums[n - 1] == 0;
    }
}
```
### Algorithm
1. Iterate through the array `nums` with an index `i` from `0` to `n-1`, where `n` is the length of `nums`.
2. If `nums[i]` is negative at any point, it's an impossible state. Return `false`.
3. If `nums[i]` is `0`, no operations are needed for this element, so continue to the next index.
4. If `nums[i]` is positive, this value represents the number of decrement operations we must apply to a subarray of size `k` starting at `i`.
5. Check if a subarray of size `k` can be formed starting at `i`. If `i + k > n`, we cannot perform the operation, and since `nums[i]` is positive, it's impossible to make it zero. Return `false`.
6. If a valid subarray can be formed, subtract `nums[i]` from all elements in the subarray `nums[i...i+k-1]`.
7. After the loop finishes, all elements from `nums[0]` to `nums[n-2]` have been processed and effectively turned to zero. The possibility of success hinges on the final value of `nums[n-1]`.
8. Return `true` if `nums[n-1]` is `0`, and `false` otherwise.

## Greedy Approach with Sliding Window
The naive simulation is slow because of the O(k) update step inside the main loop. We can optimize this by noticing that the decrements form a sliding window. Instead of applying `k` subtractions at each step, we can maintain a running sum of the operations that affect the current element. This sum, let's call it `current_effect`, can be updated in O(1) time at each step. As we move from index `i` to `i+1`, we add the effect of the new operations started at `i` and subtract the effect of the operations that just fell off the window's left edge (i.e., those started at `i-k+1`). This transforms the O(n*k) algorithm into a much faster O(n) one.
**Time:** O(n), where n is the length of `nums`. We iterate through the array only once. · **Space:** O(1), as we only use a few extra variables and modify the input array.
**Pros:** Highly efficient with linear time complexity.; Space-efficient as it modifies the array in-place.
**Cons:** The logic is more complex than the naive approach, involving a sliding window sum concept.; Modifies the input array, which might not be desirable in some contexts (though acceptable for this problem).
### Explanation
This optimized approach still follows the same greedy strategy but improves the performance by avoiding the inner loop. We iterate through the array once, maintaining a variable `current_effect` that represents the total decrement applied to the current element `nums[i]` from operations started in the range `[i-k+1, i-1]`.

At each index `i`:
1. We check if `current_effect` exceeds `nums[i]`. If it does, the element would become negative, which is impossible, so we return `false`.
2. The number of operations we must start at `i` is `ops_i = nums[i] - current_effect`.
3. We add this `ops_i` to `current_effect` because it will affect the subsequent `k-1` elements.
4. To keep track of `ops_i` for later removal from the sliding window, we can cleverly overwrite `nums[i]` with this value.
5. When our index `i` is `k-1` or greater, it means the window has moved one step, and the operation that started at `i-k+1` is no longer in effect. We subtract its value (which we stored in `nums[i-k+1]`) from `current_effect`.

After the loop, if `current_effect` is zero, it means all operations were perfectly contained within the array and the last element was successfully zeroed out. If `current_effect` is non-zero, it implies that some operations would need to extend beyond the array's bounds, which is not possible.

```java
class Solution {
    public boolean checkArray(int[] nums, int k) {
        if (k == 1) {
            return true;
        }
        int n = nums.length;
        // current_effect represents the sum of operations in the current window.
        long current_effect = 0;
        for (int i = 0; i < n; i++) {
            // If the total decrement effect is greater than the current element,
            // it means the element would become negative. Impossible.
            if (current_effect > nums[i]) {
                return false;
            }
            
            // The number of operations to start at index i is the remaining value.
            // We reuse nums[i] to store this count.
            long ops_i = nums[i] - current_effect;
            nums[i] = (int)ops_i;
            
            // Add the effect of the new operations.
            current_effect += ops_i;
            
            // If the window has moved past the k-th element,
            // remove the effect of the operation that is now out of the window.
            if (i >= k - 1) {
                current_effect -= nums[i - k + 1];
            }
        }
        
        // At the end, the current_effect must be zero. This implies that the
        // operations perfectly terminated at the end of the array, leaving
        // the final effective element nums[n-1] as zero.
        return current_effect == 0;
    }
}
```
### Algorithm
1. Handle the edge case where `k=1`. In this case, any non-negative array can be made zero, so return `true`.
2. Initialize a variable `current_effect` to `0`. This will track the cumulative effect of operations on the current element.
3. Iterate through the array `nums` with an index `i` from `0` to `n-1`.
4. If `current_effect` is greater than `nums[i]`, it means the element would become negative, which is not allowed. Return `false`.
5. Calculate the number of operations that must start at index `i`: `ops_i = nums[i] - current_effect`.
6. Update `current_effect` by adding `ops_i`, as its effect will carry over to the next elements in the window.
7. Reuse the `nums[i]` entry to store `ops_i`.
8. If `i >= k - 1`, an operation window is ending. Subtract the effect of the operation that started at `i - k + 1` (which is stored in `nums[i - k + 1]`) from `current_effect`.
9. After the loop, the `current_effect` must be zero. This ensures that no operations are 'leaking' past the end of the array, which implies the last element was correctly zeroed out. Return `true` if `current_effect == 0`, `false` otherwise.

# Solutions
### Java

```java
class Solution {
public
  boolean checkArray(int[] nums, int k) {
    int n = nums.length;
    int[] d = new int[n + 1];
    int s = 0;
    for (int i = 0; i < n; ++i) {
      s += d[i];
      nums[i] += s;
      if (nums[i] == 0) {
        continue;
      }
      if (nums[i] < 0 || i + k > n) {
        return false;
      }
      s -= nums[i];
      d[i + k] += nums[i];
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool checkArray(vector<int> &nums, int k) {
    int n = nums.size();
    vector<int> d(n + 1);
    int s = 0;
    for (int i = 0; i < n; ++i) {
      s += d[i];
      nums[i] += s;
      if (nums[i] == 0) {
        continue;
      }
      if (nums[i] < 0 || i + k > n) {
        return false;
      }
      s -= nums[i];
      d[i + k] += nums[i];
    }
    return true;
  }
};

```

### Python

```python
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

```