Watch 4 video solutions for Count Non-Decreasing Subarrays After K Operations, a hard level problem involving Array, Stack, Segment Tree. This walkthrough by Amit Choraria has 1,661 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given an array nums of n integers and an integer k.
For each subarray of nums, you can apply up to k operations on it. In each operation, you increment any element of the subarray by 1.
Note that each subarray is considered independently, meaning changes made to one subarray do not persist to another.
Return the number of subarrays that you can make non-decreasing after performing at most k operations.
An array is said to be non-decreasing if each element is greater than or equal to its previous element, if it exists.
Example 1:
Input: nums = [6,3,1,2,4,4], k = 7
Output: 17
Explanation:
Out of all 21 possible subarrays of nums, only the subarrays [6, 3, 1], [6, 3, 1, 2], [6, 3, 1, 2, 4] and [6, 3, 1, 2, 4, 4] cannot be made non-decreasing after applying up to k = 7 operations. Thus, the number of non-decreasing subarrays is 21 - 4 = 17.
Example 2:
Input: nums = [6,3,1,3,6], k = 4
Output: 12
Explanation:
The subarray [3, 1, 3, 6] along with all subarrays of nums with three or fewer elements, except [6, 3, 1], can be made non-decreasing after k operations. There are 5 subarrays of a single element, 4 subarrays of two elements, and 2 subarrays of three elements except [6, 3, 1], so there are 1 + 5 + 4 + 2 = 12 subarrays that can be made non-decreasing.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= k <= 109Problem Overview: You are given an array nums and an integer k. A subarray is valid if you can perform at most k increment operations so that the subarray becomes non-decreasing. The task is to count how many subarrays satisfy this condition.
Approach 1: Brute Force Simulation (O(n²) time, O(1) space)
Enumerate every possible subarray starting at index i and extend it to the right. While extending, simulate the minimum increments required to keep the sequence non-decreasing. Maintain the required value for the next element (the maximum seen so far). If nums[j] is smaller, add max_so_far - nums[j] to the operation cost. Stop expanding once the cost exceeds k. This method is easy to reason about and shows how the increment cost accumulates, but checking every subarray leads to O(n²) time.
Approach 2: Sliding Window with Monotonic Stack (O(n) time, O(n) space)
The optimal solution treats the problem as a dynamic window where the right pointer expands the subarray and the left pointer shrinks it when the cost exceeds k. The main challenge is efficiently tracking the number of increments needed to maintain a non-decreasing order. A monotonic stack groups elements into segments where each segment represents values that must be raised to a common height.
When a new element enters the window, merge stack segments while the top value is smaller than the incoming value. Each merge updates the cost required to raise previous elements to the new level. This effectively models the increments needed to maintain a non-decreasing sequence. The stack keeps values in decreasing order so updates happen amortized O(1) per element.
If the accumulated cost exceeds k, move the left boundary of the window forward and remove its contribution from the cost structure. Because each element is pushed and popped at most once from the stack, the total work across the array remains linear. This pattern combines a sliding window with a monotonic structure similar to techniques used in monotonic queue problems.
Every time the window expands to index r, all subarrays ending at r and starting between l and r are valid. Add r - l + 1 to the answer. The algorithm processes the array once and maintains the increment cost dynamically.
Recommended for interviews: Interviewers expect the sliding window combined with a monotonic stack. The brute force approach demonstrates understanding of how increment costs accumulate, but the optimized solution shows strong command of amortized analysis and advanced window techniques.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n²) | O(1) | Useful for understanding how increment cost accumulates when forming a non-decreasing sequence. |
| Sliding Window + Monotonic Stack | O(n) | O(n) | Best general solution for large arrays. Maintains increment cost dynamically while expanding and shrinking the window. |