Apply Operations to Make All Array Elements Equal to Zero

Med

#2489Time: 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.

Patterns

Prefix Sum

Data structures

Array

Prompt

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 <= 10⁵
0 <= nums[i] <= 10⁶

Approaches

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

Iterate through the array nums with an index i from 0 to n-1, where n is the length of nums.
If nums[i] is negative at any point, it's an impossible state. Return false.
If nums[i] is 0, no operations are needed for this element, so continue to the next index.
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.
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.
If a valid subarray can be formed, subtract nums[i] from all elements in the subarray nums[i...i+k-1].
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].
Return true if nums[n-1] is 0, and false otherwise.

Walkthrough

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.

1class Solution {2    public boolean checkArray(int[] nums, int k) {3        // With k=1, we can decrement any element individually.4        // Since all nums[i] >= 0, we can always make them 0.5        if (k == 1) {6            return true;7        }8        int n = nums.length;9        for (int i = 0; i < n; i++) {10            if (nums[i] < 0) {11                return false;12            }13            if (nums[i] == 0) {14                continue;15            }16            // If nums[i] > 0, we must perform operations.17            // This is impossible if the subarray goes out of bounds.18            if (i + k > n) {19                return false;20            }21            int ops = nums[i];22            for (int j = i; j < i + k; j++) {23                nums[j] -= ops;24            }25        }26        // If we successfully processed all elements, the last one must be 0.27        return nums[n - 1] == 0;28    }29}

Complexity

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.

Trade-offs

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.

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.

Algorithm

Handle the edge case where k=1. In this case, any non-negative array can be made zero, so return true.
Initialize a variable current_effect to 0. This will track the cumulative effect of operations on the current element.
Iterate through the array nums with an index i from 0 to n-1.
If current_effect is greater than nums[i], it means the element would become negative, which is not allowed. Return false.
Calculate the number of operations that must start at index i: ops_i = nums[i] - current_effect.
Update current_effect by adding ops_i, as its effect will carry over to the next elements in the window.
Reuse the nums[i] entry to store ops_i.
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.
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.

Walkthrough

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:

We check if current_effect exceeds nums[i]. If it does, the element would become negative, which is impossible, so we return false.
The number of operations we must start at i is ops_i = nums[i] - current_effect.
We add this ops_i to current_effect because it will affect the subsequent k-1 elements.
To keep track of ops_i for later removal from the sliding window, we can cleverly overwrite nums[i] with this value.
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.

1class Solution {2    public boolean checkArray(int[] nums, int k) {3        if (k == 1) {4            return true;5        }6        int n = nums.length;7        // current_effect represents the sum of operations in the current window.8        long current_effect = 0;9        for (int i = 0; i < n; i++) {10            // If the total decrement effect is greater than the current element,11            // it means the element would become negative. Impossible.12            if (current_effect > nums[i]) {13                return false;14            }15            16            // The number of operations to start at index i is the remaining value.17            // We reuse nums[i] to store this count.18            long ops_i = nums[i] - current_effect;19            nums[i] = (int)ops_i;20            21            // Add the effect of the new operations.22            current_effect += ops_i;23            24            // If the window has moved past the k-th element,25            // remove the effect of the operation that is now out of the window.26            if (i >= k - 1) {27                current_effect -= nums[i - k + 1];28            }29        }30        31        // At the end, the current_effect must be zero. This implies that the32        // operations perfectly terminated at the end of the array, leaving33        // the final effective element nums[n-1] as zero.34        return current_effect == 0;35    }36}

Complexity

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.

Trade-offs

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).

Solutions

Solution

1class Solution {2public3  boolean checkArray(int[] nums, int k) {4    int n = nums.length;5    int[] d = new int[n + 1];6    int s = 0;7    for (int i = 0; i < n; ++i) {8      s += d[i];9      nums[i] += s;10      if (nums[i] == 0) {11        continue;12      }13      if (nums[i] < 0 || i + k > n) {14        return false;15      }16      s -= nums[i];17      d[i + k] += nums[i];18    }19    return true;20  }21}

1class Solution {2public:3  bool checkArray(vector<int> &nums, int k) {4    int n = nums.size();5    vector<int> d(n + 1);6    int s = 0;7    for (int i = 0; i < n; ++i) {8      s += d[i];9      nums[i] += s;10      if (nums[i] == 0) {11        continue;12      }13      if (nums[i] < 0 || i + k > n) {14        return false;15      }16      s -= nums[i];17      d[i + k] += nums[i];18    }19    return true;20  }21};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem