Watch 10 video solutions for Apply Operations to Make All Array Elements Equal to Zero, a medium level problem involving Array, Prefix Sum. This walkthrough by codingMohan has 2,409 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |