Skip to content

2772. Apply Operations to Make All Array Elements Equal to Zero 👍

  • Time: $O(n)$
  • Space: $O(k)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  bool checkArray(vector<int>& nums, int k) {
    if (k == 1)
      return true;

    int needDecrease = 0;
    // Store nums[i - k + 1..i] with decreasing nums[i - k + 1].
    deque<int> dq;

    for (int i = 0; i < nums.size(); ++i) {
      if (i >= k) {
        needDecrease -= dq.front();
        dq.pop_front();
      }
      if (nums[i] < needDecrease)
        return false;
      const int decreasedNum = nums[i] - needDecrease;
      dq.push_back(decreasedNum);
      needDecrease += decreasedNum;
    }

    return dq.back() == 0;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public boolean checkArray(int[] nums, int k) {
    if (k == 1)
      return true;

    int needDecrease = 0;
    // Store nums[i - k + 1..i] with decreasing nums[i - k + 1].
    Deque<Integer> dq = new ArrayDeque<>();

    for (int i = 0; i < nums.length; ++i) {
      if (i >= k)
        needDecrease -= dq.pollFirst();
      if (nums[i] < needDecrease)
        return false;
      final int decreasedNum = nums[i] - needDecrease;
      dq.offerLast(decreasedNum);
      needDecrease += decreasedNum;
    }

    return dq.getLast() == 0;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def checkArray(self, nums: list[int], k: int) -> bool:
    if k == 1:
      return True

    needDecrease = 0
    # Store nums[i - k + 1..i] with decreasing nums[i - k + 1].
    dq = collections.deque()

    for i, num in enumerate(nums):
      if i >= k:
        needDecrease -= dq.popleft()
      if nums[i] < needDecrease:
        return False
      decreasedNum = nums[i] - needDecrease
      dq.append(decreasedNum)
      needDecrease += decreasedNum

    return dq[-1] == 0