Count Non-Decreasing Subarrays After K Operations

Count Non-Decreasing Subarrays After K Operations

What is this problem about?

This "Hard" coding problem asks you to find the number of subarrays that can be made non-decreasing by performing at most $k$ total operations. An operation consists of choosing an element and increasing it. You want to make each element in the subarray greater than or equal to its predecessor using the minimum number of increases.

Why is this asked in interviews?

Google and Microsoft use this problem to test mastery of complex sliding window logic and monotonic data structures. It requires you to calculate the "cost" of making a window non-decreasing dynamically. This involves tracking peaks and calculating the volume of "fills" needed to level out the valleys, making it a very high-level algorithmic challenge.

Algorithmic pattern used

This problem uses the Sliding Window pattern combined with a Monotonic Queue (or Monotonic Stack).

1. Use two pointers (left, right) to represent the current subarray.
2. Maintain a monotonic queue to keep track of the maximum elements in the window that act as "ceilings" for non-decreasing segments.
3. As the right pointer moves, add the cost of increasing nums[right] to match the current required height.
4. If the total cost exceeds $k$, move the left pointer and subtract the cost associated with the removed element.
5. Each valid window $[left, right]$ adds right - left + 1 to the total count.

Example explanation

nums = [3, 1, 2], $k = 2$.

• Window [3]: Cost 0. Count = 1.
• Window [3, 1]: To make non-decreasing, 1 must become 3. Cost = 2. Total cost $2 \le k$. Count = 1 + 2 = 3.
• Window [3, 1, 2]: 1 becomes 3, 2 becomes 3. Cost = $(3-1) + (3-2) = 3$. $3 > k$.
• Move left: Window [1, 2]. Cost 0. Count = 3 + 2 = 5.
• Window [2]: Cost 0. Count = 5 + 1 = 6.

Common mistakes candidates make

Calculating the cost during the left pointer contraction is the hardest part. Many candidates struggle to efficiently determine how much "cost" was contributed by the element being removed, especially when it was part of a sequence leveled by a much larger element. Another mistake is using a Segment Tree for range sums, which might be too slow ($O(n \log n)$ vs $O(n)$).

Interview preparation tip

Master the "Monotonic Queue" for sliding window maximum problems. It's the foundation for many "Hard" array problems where you need to know the influence of a dominant element over a dynamic range.