3420. Count Non-Decreasing Subarrays After K Operations
Problem Overview
Making a subarray non-decreasing means raising every position up to the maximum value seen to its left inside that subarray.
Intuition
Making a subarray non-decreasing means raising every position up to the maximum value seen to its left inside that subarray. The total raise is the operation cost. Longer windows never cost less, so for each left end there is a farthest right end whose cost still fits in k. Scanning from right to left builds a window [i, j] and a monotonic deque of indices whose values act as the live left maxima after those raises. When nums[i] enters, every smaller segment to its right is lifted to nums[i], and the cost grows by the segment length times the lift. While the cost is larger than k, the rightmost index is dropped and its lift is refunded. Once the window is affordable again, every subarray that starts at i and ends anywhere from i through j is valid, so j minus i plus 1 is added to the answer. Each index enters and leaves the deque once, so the walk is linear.
Algorithm
- 1Start with an empty array deque and cost 0, and set both pointers at the last index.
- 2For each left index i from right to left, pop every deque back index whose value is smaller than nums[i] and add the raise cost for that segment.
- 3Push i onto the deque.
- 4While cost is greater than k, subtract the lift of the current rightmost index and move j left, popping the deque front when it equals j.
- 5Add j minus i plus 1 to the answer.
- 6Return the total after every left index is processed.
Example Walkthrough
Input: nums = [6, 3, 1, 2, 4, 4], k = 7
- 1.There are 21 subarrays in total. Four of them need more than 7 raises to become non-decreasing: [6,3,1], [6,3,1,2], [6,3,1,2,4], and [6,3,1,2,4,4].
- 2.Every other subarray fits inside the budget of 7 operations.
- 3.So the count is 21 minus 4, which is 17.
Output: 17
Common Pitfalls
- •Use 64 bit integers for the cost and the answer. A raise of a large value across many positions overflows a 32 bit integer.
- •Each subarray is independent. Raises used for one window do not carry over to another.
- •Shrink from the right when the cost exceeds k. Growing only the left pointer without refunding the rightmost lift breaks the window cost.
- •The deque stores indices, not values. The segment length between consecutive deque indices is what multiplies the lift.
// Approach: Scan right to left. A window [i, j] stores the cheapest cost to
// make nums[i..j] non-decreasing by raising each position to the running
// left maximum. A monotonic deque of indices keeps those maxima in order.
// When nums[i] enters, every smaller segment to its right is raised to it and
// the cost grows by length times the lift. While cost exceeds k, drop the
// rightmost index and refund its lift. Every valid right end for the current
// left adds j - i + 1 subarrays. Each index enters and leaves the deque once.
// Time: O(n) Space: O(n)
public class Solution
{
public long CountNonDecreasingSubarrays(int[] nums, int k)
{
int n = nums.Length;
long ans = 0;
long cost = 0;
int[] dq = new int[n];
int head = 0, tail = 0;
for (int i = n - 1, j = n - 1; i >= 0; --i)
{
int num = nums[i];
while (head < tail && nums[dq[tail - 1]] < num)
{
int l = dq[--tail];
int r = head == tail ? j + 1 : dq[tail - 1];
cost += (long)(r - l) * (num - nums[l]);
}
dq[tail++] = i;
while (cost > k)
{
cost -= nums[dq[head]] - nums[j];
if (dq[head] == j)
++head;
--j;
}
ans += j - i + 1;
}
return ans;
}
}