Apply Operations to Make All Array Elements Equal to Zero

MEDIUM

Description

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

Checkout 2 different approaches to solve Apply Operations to Make All Array Elements Equal to Zero. Click on different approaches to view the approach and algorithm in detail.

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.

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.

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 Analysis

Time Complexity: 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 Complexity: O(1) as we modify the array in-place and use a constant amount of extra space.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Apply Operations to Make All Array Elements Equal to Zero. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Apply Operations to Make All Array Elements Equal to Zero

Patterns:

Prefix Sum

Data Structures:

Array