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:
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 <= 10^5
0 <= nums[i] <= 10^6
A brute-force approach would be to iterate through the array. If an element nums[i]
is greater than 0, then iterate through all subarrays of size k
starting at index i
. If nums[i]
is still greater than 0 after checking all such subarrays, or if we can't find a valid subarray, return false.
This approach would involve repeated iterations, resulting in a high time complexity.
def solve_naive(nums, k):
n = len(nums)
def decrease_subarray(start_index, amount):
for i in range(start_index, min(start_index + k, n)):
nums[i] -= amount
for i in range(n):
if nums[i] > 0:
can_decrease = False
for j in range(min(i + 1, n - k + 1)):
if i >= j and i < j + k:
decrease_subarray(j, nums[i])
can_decrease = True
break
if not can_decrease and nums[i] > 0:
return False
return all(x == 0 for x in nums)
Time Complexity: O(N*M), where N is the length of nums, and M is related to the number of subarrays that might need to be examined.
Space Complexity: O(1)
The optimal approach involves using a difference array to keep track of the changes made by the operations. Iterate through the nums
array. At each index i
, check if nums[i]
is greater than the current accumulated decrease. If it is, then we need to apply the operation on the subarray starting at index i
. Update the difference array to reflect this operation. If nums[i]
is less than the current accumulated decrease, then it is impossible to make all elements zero.
k > len(nums)
: The subarray size cannot be greater than the array length; should return false.def solve(nums, k):
n = len(nums)
diff = [0] * n
curr_sum = 0
for i in range(n):
curr_sum += diff[i]
if nums[i] < curr_sum:
return False
needed_reduction = nums[i] - curr_sum
if needed_reduction > 0:
if i + k > n:
return False
curr_sum += needed_reduction
if i + k < n:
diff[i + k] -= needed_reduction
return True
Time Complexity: O(N), where N is the length of the nums
array.
Space Complexity: O(N), due to the diff
array.