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 to0 ,orfalse otherwise.

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

Examples

Example 1

1
2
3
4
5
6

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

1
2
3

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^5
  • 0 <= nums[i] <= 10^6

Solution

Method 1 – Greedy with Prefix Sum

Intuition

The key idea is to always reduce the leftmost non-zero element as much as possible using the allowed operation. By greedily applying the operation starting from the left, and tracking the cumulative effect of all operations using a prefix sum (difference array), we can efficiently determine if it’s possible to make all elements zero.

Approach

  1. Initialize a difference array diff of size n+1 (where n is the length of nums) to track the net effect of operations.
  2. Iterate through the array from left to right.
  • At each index i, update the running sum of operations applied so far.
  • If after applying all previous operations, nums[i] is still greater than zero:
    • If there are at least k elements remaining from i, apply the operation enough times to make nums[i] zero.
    • Update the difference array to reflect this operation.
    • If not enough elements remain, return False.
  1. If the loop completes, return True.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

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

class Solution {
   public boolean checkArray(int[] nums, int k) {
      int n = nums.length;
      int[] diff = new int[n + 1];
      int curr = 0;
      for (int i = 0; i < n; ++i) {
        curr += diff[i];
        int val = nums[i] + curr;
        if (val < 0) return false;
        if (val == 0) continue;
        if (i + k > n) return false;
        curr -= val;
        diff[i + k] += val;
      }
      return true;
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
   def checkArray(self, nums: list[int], k: int) -> bool:
      n = len(nums)
      diff = [0] * (n + 1)
      curr = 0
      for i in range(n):
        curr += diff[i]
        val = nums[i] + curr
        if val < 0:
           return False
        if val == 0:
           continue
        if i + k > n:
           return False
        curr -= val
        diff[i + k] += val
      return True

Complexity

  • ⏰ Time complexity: O(n) — Each element is processed once.
  • 🧺 Space complexity: O(n) — For the difference array.