Scale Engineer

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 <= 105
  • 0 <= nums[i] <= 106

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

  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.

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.

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;    }}

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.

Solutions

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;  }}

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 →

Next problem