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] <= 106Problem Overview: You get an integer array nums and a window size k. One operation subtracts 1 from every element in a subarray of length k. The task is to determine whether a sequence of such operations can reduce every value in the array to exactly zero.
Approach 1: Simplified Operations Tracking with Prefix Sum (O(n) time, O(n) space)
The key observation: when you reach index i, all operations that started earlier and still affect this index must already be accounted for. Track the cumulative number of active operations using a difference array. When the effective value at i (nums[i] - appliedOps) is positive, you must start exactly that many operations at i so the element becomes zero. Record their effect using a difference array so their influence automatically expires after k positions. If i + k exceeds the array length while you still need operations, making the array zero is impossible. This greedy sweep works because delaying an operation would leave the current index non‑zero. The technique relies on prefix accumulation similar to prefix sum or difference arrays and processes the array once.
Approach 2: Segment Tree for Operations Management (O(n log n) time, O(n) space)
A more general simulation uses a segment tree to support range decrement operations and point queries. Iterate from left to right, query the current value at index i, and if it is positive, apply that many range updates over [i, i + k - 1]. The segment tree efficiently propagates lazy updates so each operation runs in O(log n). This approach models the operations explicitly and is useful when constraints require flexible range updates or additional queries. However, it is slower and more complex than the greedy prefix-sum method for this problem.
Recommended for interviews: The greedy difference-array solution is the expected approach. It combines insights from array processing and prefix sum techniques to simulate range operations in constant time per index. A brute-force or segment-tree simulation shows understanding, but the O(n) greedy pass demonstrates strong algorithmic intuition and is typically what interviewers look for.
In this approach, we'll apply a greedy strategy to reduce the operations needed. By treating the decrement operations as intervals and tracking the prefix sum of these intervals, we can minimize the number of decrement operations efficiently.
Essentially, for each element in the array, we determine how many times a decrement operation needs to be applied so that every element becomes zero. By working with cumulative differences, we avoid redundant work and make the decision-making process more efficient.
This Python code uses a simple greedy approach by treating the decrement operation as intervals using a prefix sum technique. We apply operations only when necessary and track when we reverse these operations when they are no longer necessary.
Time Complexity: O(n), where n is the number of elements in the array, due to a single pass through the array with constant-time operations. Space Complexity: O(n), for the operations array used to track increment reversals.
This approach employs a segment tree to efficiently manage operations over any subarray. By leveraging the segment tree, we can handle range updates and queries in logarithmic time, significantly optimizing performance over naive approaches.
The segment tree allows efficient application of operations to any range and effectively checks if the range operations can make the entire array zero.
This C++ solution utilizes a segment tree to manage operations across multiple indices. It checks feasibility by calculating required operations per segment and efficiently applies them using range updates.
C++
Time Complexity: O(n log n), Space Complexity: O(n) due to segment tree storage.
First, let's consider the first element of nums, nums[0]:
nums[0] = 0, we don't need to do anything.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].
nums[i] = 0, there's no need for any operation, and we can skip directly.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].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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Simplified Operations Tracking | Time Complexity: O(n), where n is the number of elements in the array, due to a single pass through the array with constant-time operations. Space Complexity: O(n), for the operations array used to track increment reversals. |
| Segment Tree for Operations Management | Time Complexity: O(n log n), Space Complexity: O(n) due to segment tree storage. |
| Difference Array + Prefix Sum | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Simplified Operations Tracking (Difference / Prefix Sum) | O(n) | O(n) | Best general solution. Efficient when range updates always have fixed length k. |
| Segment Tree for Range Updates | O(n log n) | O(n) | Useful if the problem extends to dynamic queries or variable-length range operations. |
O(NlogK), O(N) | 2772. Apply Operations to Make All Array Elements Equal to 0 | Leetcode Weekly 353 • codingMohan • 2,409 views views
Watch 9 more video solutions →Practice Apply Operations to Make All Array Elements Equal to Zero with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor