Count Non-Decreasing Subarrays After K Operations - Solution & Explanation

Problem 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.