LeetCode 2772. Apply Operations to Make All Array Elements Equal to Zero Solution in Java, C++, Python & More | Explanation + Code

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

Solutions

Solution 1: Difference Array + Prefix Sum

First, let's consider the first element of nums, nums[0]:

• If nums[0] = 0, we don't need to do anything.
• If nums[0] > 0, we need to operate on nums[0..k-1] for nums[0] times, subtracting nums[0] from all elements in nums[0..k-1], so nums[0] becomes 0.

To perform the add and subtract operations on a contiguous segment of elements simultaneously, we can use a difference array to manage these operations. We represent the difference array with d[i], and calculating the prefix sum of the difference array gives us the change of the value at each position.

Therefore, we iterate over nums. For each element nums[i], the current position's change quantity is s = ∑_{j=0}ⁱ d[j]. We add s to nums[i] to get the actual value of nums[i].

• If nums[i] = 0, there's no need for any operation, and we can skip directly.
• If nums[i]=0 or i + k > n, it indicates that after the previous operations, nums[i] has become negative, or nums[i..i+k-1] is out of bounds. Therefore, it's impossible to make all elements in nums equal to 0. We return false. Otherwise, we need to subtract nums[i] from all elements in the interval [i..i+k-1]. Therefore, we subtract nums[i] from s and add nums[i] to d[i+k].
• We continue to iterate over the next element.

If the iteration ends, it means that all elements in nums can be made equal to 0, so we return true.

The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.

PythonJavaC++GoTypeScript

class Solution: def checkArray(self, nums: List[int], k: int) -> bool: n = len(nums) d = [0] * (n + 1) s = 0 for i, x in enumerate(nums): s += d[i] x += s if x == 0: continue if x < 0 or i + k > n: return False s -= x d[i + k] += x return True(code-box)

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; } }(code-box)

class Solution { public: bool checkArray(vector<int>& nums, int k) { int n = nums.size(); vector<int> d(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; } };(code-box)

func checkArray(nums []int, k int) bool { n := len(nums) d := make([]int, n+1) s := 0 for i, x := range nums { s += d[i] x += s if x == 0 { continue } if x < 0 || i+k > n { return false } s -= x d[i+k] += x } return true }(code-box)

function checkArray(nums: number[], k: number): boolean { const n = nums.length; const d: number[] = Array(n + 1).fill(0); let s = 0; for (let 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; }(code-box)