2772. Apply Operations to Make All Array Elements Equal to Zero
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 by1
.
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 = \sum_{j=0}^{i} 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$.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|