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 <= 1050 <= nums[i] <= 106In #2772 Apply Operations to Make All Array Elements Equal to Zero, you are allowed to repeatedly choose a subarray of length k and decrease every element in that subarray by 1. The goal is to determine whether it is possible to make every element in the array equal to zero.
A key observation is that operations affect k consecutive elements, which makes this problem suitable for a greedy strategy combined with a prefix sum (difference array). While scanning the array from left to right, track how many decrement operations are currently affecting the position. If the effective value of the current element is still positive, you must start operations at that index to eliminate the remaining value.
To efficiently apply these operations without repeatedly updating k elements, use a difference array to mark when the effect of an operation begins and ends. If at any point an operation would exceed array bounds or produce a negative value, the transformation is impossible. This approach processes the array in linear time.
Time Complexity: O(n) with a single pass.
Space Complexity: O(n) for the difference array used to simulate range updates.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Greedy with Prefix Sum (Difference Array) | O(n) | O(n) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
In case it is possible, then how can you do the operations? which subarrays do you choose and in what order?
The order of the chosen subarrays should be from the left to the right of the array
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Each operation affects a continuous range of k elements. A difference array allows you to simulate these range updates in constant time by marking where the operation starts and ends. The running prefix sum then tells you how many active operations affect the current index.
Problems involving range updates, greedy decisions, and prefix sums are common in FAANG-style interviews. While this exact problem may vary, the underlying technique of using difference arrays for efficient range operations is frequently tested.
The optimal approach uses a greedy strategy with a prefix sum or difference array. By scanning from left to right, you determine how many operations must start at each index and track their cumulative effect efficiently. This avoids repeatedly updating k elements and keeps the solution linear.
A difference array combined with prefix sum tracking works best. It efficiently handles repeated range updates and helps maintain the cumulative effect of previous operations while iterating through the array.