LeetCode 3420 - Count Non-Decreasing Subarrays After K Operations

You are given an array nums and a budget of at most k increment operations. For any chosen subarray, you may repeatedly pick an element inside that subarray and increase it by 1.

leetcodehardarraystacksegment-treequeuesliding-windowmonotonic-stackmonotonic-queue

LeetCode Problem 3420

Difficulty: 🔴 Hard
Topics: Array, Stack, Segment Tree, Queue, Sliding Window, Monotonic Stack, Monotonic Queue

Solution

Problem Understanding

You are given an array nums and a budget of at most k increment operations.

For any chosen subarray, you may repeatedly pick an element inside that subarray and increase it by 1. The goal is to determine whether that subarray can be transformed into a non-decreasing array using no more than k total increments.

A non-decreasing array satisfies:

$$a[i] \ge a[i - 1]$$

for every valid index i.

The important detail is that each subarray is evaluated independently. Operations used for one subarray do not affect any other subarray.

The task is not to find the minimum number of operations for a single subarray. Instead, we must count how many of the O(n²) possible subarrays can be made non-decreasing within the given budget.

The constraints are extremely large:

  • n can be as large as 100000
  • Values can be up to 10^9
  • k can be up to 10^9

Because there are up to roughly five billion subarrays when n = 100000, explicitly checking every subarray is impossible.

To understand the required operations, consider a subarray:

[6, 3, 1, 2]

To make it non-decreasing, we must raise every element that is smaller than the maximum value seen to its left:

[6, 6, 6, 6]

The required cost is:

(6 - 3) + (6 - 1) + (6 - 2) = 11

This observation is the foundation of the optimal solution.

Important edge cases include:

  • Arrays that are already non-decreasing, every subarray is valid.
  • Strictly decreasing arrays, many subarrays require large costs.
  • Very large values, which require 64-bit arithmetic.
  • Very large k, where almost every subarray becomes valid.
  • Single-element arrays, which always require zero operations.

Approaches

Brute Force

The most direct solution is to examine every subarray.

For each subarray [l, r], we compute the minimum number of increments needed to make it non-decreasing.

This can be done by scanning from left to right:

target = nums[l]

for each next element:
    if nums[i] < target:
        cost += target - nums[i]
    else:
        target = nums[i]

If the resulting cost is at most k, we count the subarray.

This approach is correct because it explicitly computes the minimum operations required for every subarray.

Unfortunately:

  • There are O(n²) subarrays.
  • Computing each cost takes O(n) time.

The total complexity becomes O(n³).

Even with some optimization to reuse work, the complexity remains far too large for n = 100000.

Key Insight

For a fixed subarray, the final non-decreasing form is obtained by repeatedly propagating the maximum value seen so far.

Instead of processing subarrays independently, we can process all subarrays simultaneously using a sliding window.

The clever observation is that if we scan from right to left, we can maintain:

  • A window [i, j]
  • The total cost needed to make that window non-decreasing
  • A monotonic deque describing the adjusted values inside the window

When a new element is added on the left:

nums[i]

it may force several smaller adjusted values to increase.

A monotonic deque allows us to update that cost efficiently.

If the cost exceeds k, we shrink the right boundary until the window becomes valid again.

Since every index enters and leaves the deque at most once, the entire algorithm runs in linear time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n³) O(1) Checks every subarray independently
Optimal O(n) O(n) Sliding window with monotonic deque

Algorithm Walkthrough

We process the array from right to left.

The deque stores indices whose corresponding values form a non-increasing sequence.

The deque represents the "plateaus" that appear after performing the necessary increments.

1. Initialize the sliding window

We maintain:

  • i, left boundary
  • j, right boundary
  • cost, operations needed for current window
  • deque, monotonic structure
  • answer

Initially:

i = n - 1
j = n - 1
cost = 0

2. Add a new element on the left

Suppose we are inserting:

nums[i]

into the current window.

If some values already stored in the deque are smaller than nums[i], those values must be raised to match nums[i].

Therefore we repeatedly pop smaller values.

3. Update the cost

Assume a popped index is l.

That value affects a segment:

[l, r)

where r is the next index remaining in the deque.

All elements in that segment must now be increased from:

nums[l]

to:

nums[i]

Additional cost:

$$(r-l)\times(nums[i]-nums[l])$$

We add this to the running cost.

4. Insert the new index

After all smaller values are removed, we push i into the deque.

The deque remains monotonic.

5. Shrink the window if necessary

If:

cost > k

the current window is invalid.

We repeatedly move the right boundary leftward.

When removing nums[j], we subtract its contribution:

nums[dq.front()] - nums[j]

If the removed index equals the deque front, remove it from the deque.

Continue until:

cost <= k

6. Count valid subarrays

At this point, every subarray:

[i, i]
[i, i + 1]
...
[i, j]

is valid.

The count contributed by this position is:

j - i + 1

Add this to the answer.

7. Continue for all positions

Repeat until every index has been used as a left boundary.

Why it works

The deque maintains the piecewise-constant structure of the array after all required increments are applied.

Whenever a larger value is inserted from the left, every smaller plateau that it dominates is merged into a new plateau, and the exact additional operation cost is added.

The sliding window invariant is:

cost always equals the minimum number of increments required to make the current window non-decreasing.

Therefore:

  • If cost <= k, the window is valid.
  • If cost > k, the window is invalid.

The right boundary is moved only until the invariant becomes valid again.

Since each index enters and leaves the deque once, the algorithm remains linear.

Python Solution

from collections import deque
from typing import List

class Solution:
    def countNonDecreasingSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)

        dq = deque()
        cost = 0
        ans = 0

        j = n - 1

        for i in range(n - 1, -1, -1):
            while dq and nums[dq[-1]] < nums[i]:
                left = dq.pop()
                right = dq[-1] if dq else j + 1

                cost += (right - left) * (nums[i] - nums[left])

            dq.append(i)

            while cost > k:
                cost -= nums[dq[0]] - nums[j]

                if dq[0] == j:
                    dq.popleft()

                j -= 1

            ans += j - i + 1

        return ans

The implementation follows the algorithm directly.

The deque stores indices rather than values. This allows us to determine how many positions belong to a plateau when a merge occurs.

The first while loop performs plateau merging. Every popped segment becomes part of a larger plateau whose height is nums[i]. The exact increase in required operations is added to cost.

After inserting the new index, the second while loop ensures that the operation budget remains within k. Whenever the budget is exceeded, the window is shrunk from the right side.

Once the window becomes valid again, every ending position between i and j forms a valid subarray, so j - i + 1 is added to the answer.

All arithmetic involving costs uses Python integers, which automatically support arbitrary precision.

Go Solution

func countNonDecreasingSubarrays(nums []int, k int) int64 {
	n := len(nums)

	dq := make([]int, 0)
	var cost int64 = 0
	var ans int64 = 0

	j := n - 1

	for i := n - 1; i >= 0; i-- {
		for len(dq) > 0 && nums[dq[len(dq)-1]] < nums[i] {
			left := dq[len(dq)-1]
			dq = dq[:len(dq)-1]

			right := j + 1
			if len(dq) > 0 {
				right = dq[len(dq)-1]
			}

			cost += int64(right-left) * int64(nums[i]-nums[left])
		}

		dq = append(dq, i)

		for cost > int64(k) {
			cost -= int64(nums[dq[0]] - nums[j])

			if dq[0] == j {
				dq = dq[1:]
			}

			j--
		}

		ans += int64(j - i + 1)
	}

	return ans
}

The Go implementation is nearly identical.

The main difference is that every quantity related to operation counts uses int64. The maximum possible cost can be much larger than a 32-bit integer.

The deque is implemented using a slice. Elements are appended at the back and removed from either end through slice operations.

Worked Examples

Example 1

nums = [6,3,1,2,4,4]
k = 7

Process from right to left.

Step i Window Cost Valid Count Added
Start 5 [4] 0 1
Add 4 4 [4,4] 0 2
Add 2 3 [2,4,4] 0 3
Add 1 2 [1,2,4,4] 0 4
Add 3 1 [3,1,2,4,4] 3 5
Add 6 0 cost becomes 14 shrink window 2

The valid counts added are:

1 + 2 + 3 + 4 + 5 + 2 = 17

Final answer:

17

Example 2

nums = [6,3,1,3,6]
k = 4
Step i Cost After Update Window Valid? Added
4 0 Yes 1
3 0 Yes 2
2 0 Yes 3
1 2 Yes 4
0 8 No, shrink 2

Total:

1 + 2 + 3 + 4 + 2 = 12

Final answer:

12

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each index enters and leaves the deque at most once
Space O(n) Deque can store up to n indices

The key reason the algorithm is linear is amortization. Every index is pushed into the deque once and popped once. The window boundaries also move monotonically. Therefore all deque operations across the entire execution sum to O(n).

Test Cases

sol = Solution()

assert sol.countNonDecreasingSubarrays([6, 3, 1, 2, 4, 4], 7) == 17  # example 1
assert sol.countNonDecreasingSubarrays([6, 3, 1, 3, 6], 4) == 12  # example 2

assert sol.countNonDecreasingSubarrays([1], 1) == 1  # single element

assert sol.countNonDecreasingSubarrays([1, 2, 3, 4], 0) == 10  # already non-decreasing

assert sol.countNonDecreasingSubarrays([4, 3, 2, 1], 0) == 4  # only length-1 subarrays

assert sol.countNonDecreasingSubarrays([5, 5, 5, 5], 0) == 10  # all equal

assert sol.countNonDecreasingSubarrays([10, 1], 9) == 3  # exact budget

assert sol.countNonDecreasingSubarrays([10, 1], 8) == 2  # budget just below requirement

assert sol.countNonDecreasingSubarrays([1000000000, 1], 999999999) == 3  # large values

assert sol.countNonDecreasingSubarrays([5, 4, 3, 2, 1], 1000000000) == 15  # huge budget

assert sol.countNonDecreasingSubarrays([3, 1, 2], 2) == 6  # all subarrays valid

assert sol.countNonDecreasingSubarrays([3, 1, 2], 1) == 5  # one invalid subarray

Test Summary

Test Why
[6,3,1,2,4,4], 7 Official example
[6,3,1,3,6], 4 Official example
[1] Minimum size input
[1,2,3,4], 0 Already non-decreasing
[4,3,2,1], 0 Strictly decreasing
[5,5,5,5], 0 Equal values
[10,1], 9 Cost exactly equals budget
[10,1], 8 Budget just insufficient
[1000000000,1] Large integer handling
Large budget case Almost every subarray valid
[3,1,2], 2 Boundary where all become valid
[3,1,2], 1 Boundary where one becomes invalid

Edge Cases

Single Element Arrays

A subarray of length one is already non-decreasing. No operations are required.

This case is important because many sliding window implementations accidentally assume at least two elements exist. The algorithm handles it naturally because the cost remains zero and the window contributes exactly one valid subarray.

Strictly Decreasing Arrays

Consider:

[5,4,3,2,1]

Every longer subarray requires many increments.

This is a good stress test because it generates the largest possible costs and causes frequent window shrinking. The monotonic deque efficiently merges all smaller plateaus, keeping the complexity linear.

Very Large Values

Consider:

[1000000000, 1]

The required cost is:

999999999

Using 32-bit arithmetic can overflow when larger windows are involved. The implementation uses Python's arbitrary-precision integers and int64 in Go, ensuring correctness for the maximum constraints.

Budget Exactly Equal to Required Cost

If a subarray needs exactly k operations, it is still valid.

Many implementations mistakenly use a strict inequality and reject such windows. The algorithm only shrinks while:

cost > k

which correctly preserves subarrays whose cost equals the budget.

Large Valid Windows

When k is extremely large, the optimal window may span almost the entire array.

The algorithm handles this efficiently because the right boundary never moves unnecessarily, and every index is processed only once. This preserves the O(n) complexity even when nearly all subarrays are valid.

Sources consulted for problem statement and reference solutions: