2772. Apply Operations to Make All Array Elements Equal to Zero LeetCode Solution

In this guide, you will get 2772. Apply Operations to Make All Array Elements Equal to Zero LeetCode Solution with the best time and space complexity. The solution to Apply Operations to Make All Array Elements Equal to Zero problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

  1. Problem Statement
  2. Complexity Analysis
  3. Apply Operations to Make All Array Elements Equal to Zero solution in C++
  4. Apply Operations to Make All Array Elements Equal to Zero solution in Java
  5. Apply Operations to Make All Array Elements Equal to Zero solution in Python
  6. Additional Resources
2772. Apply Operations to Make All Array Elements Equal to Zero LeetCode Solution image

Problem Statement of Apply Operations to Make All Array Elements Equal to Zero

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

See also  498. Diagonal Traverse LeetCode Solution

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

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(k)

2772. Apply Operations to Make All Array Elements Equal to Zero LeetCode Solution in C++

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;
  }
};
/* code provided by PROGIEZ */

2772. Apply Operations to Make All Array Elements Equal to Zero LeetCode Solution in Java

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;
  }
}
// code provided by PROGIEZ

2772. Apply Operations to Make All Array Elements Equal to Zero LeetCode Solution in Python

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
# code by PROGIEZ

Additional Resources

See also  923. 3Sum With Multiplicity LeetCode Solution

Happy Coding! Keep following PROGIEZ for more updates and solutions.