Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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 summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Stack · Segment Tree · Sliding Window · Monotonic Queue
[6,3,1,2,4,4] 7
[6,3,1,3,6] 4
non-decreasing-array)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3420: Count Non-Decreasing Subarrays After K Operations
class Solution {
public long countNonDecreasingSubarrays(int[] nums, int k) {
long ans = 0;
long cost = 0;
// Store (number, count) pairs in non-increasing order. The numbers in the
// queue represent what nums[i..j] look like after adjustments.
Deque<Pair<Integer, Integer>> dq = new ArrayDeque<>();
for (int i = nums.length - 1, j = nums.length - 1; i >= 0; --i) {
final int num = nums[i];
int count = 1;
while (!dq.isEmpty() && dq.getLast().getKey() < num) {
final int nextNum = dq.getLast().getKey();
final int nextCount = dq.removeLast().getValue();
count += nextCount;
// Adjust `nextNum`s to `num`.
cost += (long) (num - nextNum) * nextCount;
}
dq.offerLast(new Pair<>(num, count));
while (cost > k) {
final int rightmostNum = dq.getFirst().getKey();
final int rightmostCount = dq.removeFirst().getValue();
cost -= (long) (rightmostNum - nums[j--]);
if (rightmostCount > 1)
dq.offerFirst(new Pair<>(rightmostNum, rightmostCount - 1));
}
ans += j - i + 1;
}
return ans;
}
}
// Accepted solution for LeetCode #3420: Count Non-Decreasing Subarrays After K Operations
package main
import "slices"
// https://space.bilibili.com/206214
func countNonDecreasingSubarrays(nums []int, k int) (ans int64) {
n := len(nums)
cnt := 0
type pair struct{ val, size int } // 根节点的值, 树的大小
q := []pair{}
r := n - 1
for l, x := range slices.Backward(nums) {
// x 进入窗口
size := 1 // 统计以 x 为根的树的大小
for len(q) > 0 && x >= q[len(q)-1].val {
// 以 p.val 为根的树，现在合并到 x 的下面（x 和 val 连一条边）
p := q[len(q)-1]
q = q[:len(q)-1]
size += p.size
cnt += (x - p.val) * p.size // 树 p.val 中的数都变成 x
}
q = append(q, pair{x, size})
// 当 cnt 大于 k 时，缩小窗口
for cnt > k {
p := &q[0] // 最右边的树
// 操作次数的减少量，等于 nums[r] 所在树的根节点值减去 nums[r]
cnt -= p.val - nums[r]
r--
// nums[r] 离开窗口后，树的大小减一
p.size--
if p.size == 0 { // 这棵树是空的
q = q[1:]
}
}
ans += int64(r - l + 1)
}
return
}
func countNonDecreasingSubarrays2(nums []int, k int) (ans int64) {
n := len(nums)
g := make([][]int, n)
posR := make([]int, n)
st := []int{}
for i, x := range nums {
for len(st) > 0 && x >= nums[st[len(st)-1]] {
posR[st[len(st)-1]] = i
st = st[:len(st)-1]
}
// 循环结束后，栈顶就是左侧 > x 的最近元素了
if len(st) > 0 {
left := st[len(st)-1]
g[left] = append(g[left], i)
}
st = append(st, i)
}
for _, i := range st {
posR[i] = n
}
cnt := 0
l := 0
q := []int{} // 单调队列维护最大值
for r, x := range nums {
// x 进入窗口
for len(q) > 0 && nums[q[len(q)-1]] <= x {
q = q[:len(q)-1] // 维护 q 的单调性
}
q = append(q, r)
// 由于队首到队尾单调递减，所以窗口最大值就是队首
cnt += nums[q[0]] - x
// 操作次数太多，缩小窗口
for cnt > k {
out := nums[l] // 离开窗口的元素
for _, i := range g[l] {
if i > r {
break
}
cnt -= (out - nums[i]) * (min(posR[i], r+1) - i)
}
l++
// 队首已经离开窗口了
if q[0] < l {
q = q[1:]
}
}
ans += int64(r - l + 1)
}
return
}
# Accepted solution for LeetCode #3420: Count Non-Decreasing Subarrays After K Operations
class Solution:
def countNonDecreasingSubarrays(self, nums: list[int], k: int) -> int:
ans = 0
cost = 0
# Store (number, count) pairs in non-increasing order. The numbers in the
# queue represent what nums[i..j] look like after adjustments.
dq = collections.deque()
j = len(nums) - 1
for i, num in reversed(list(enumerate(nums))):
count = 1
while dq and dq[-1][0] < num:
nextNum, nextCount = dq.pop()
count += nextCount
cost += (num - nextNum) * nextCount # Adjust `nextNum`s to `num`.
dq.append((num, count))
while cost > k: # Remove the rightmost number.
rightmostNum, rightmostCount = dq.popleft()
cost -= (rightmostNum - nums[j])
j -= 1
if rightmostCount > 1:
dq.appendleft((rightmostNum, rightmostCount - 1))
ans += j - i + 1
return ans
// Accepted solution for LeetCode #3420: Count Non-Decreasing Subarrays After K Operations
// Rust example auto-generated from java reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
pub fn rust_example() {
// Port the logic from the reference block below.
}
}
// Reference (java):
// // Accepted solution for LeetCode #3420: Count Non-Decreasing Subarrays After K Operations
// class Solution {
// public long countNonDecreasingSubarrays(int[] nums, int k) {
// long ans = 0;
// long cost = 0;
// // Store (number, count) pairs in non-increasing order. The numbers in the
// // queue represent what nums[i..j] look like after adjustments.
// Deque<Pair<Integer, Integer>> dq = new ArrayDeque<>();
//
// for (int i = nums.length - 1, j = nums.length - 1; i >= 0; --i) {
// final int num = nums[i];
// int count = 1;
// while (!dq.isEmpty() && dq.getLast().getKey() < num) {
// final int nextNum = dq.getLast().getKey();
// final int nextCount = dq.removeLast().getValue();
// count += nextCount;
// // Adjust `nextNum`s to `num`.
// cost += (long) (num - nextNum) * nextCount;
// }
// dq.offerLast(new Pair<>(num, count));
// while (cost > k) {
// final int rightmostNum = dq.getFirst().getKey();
// final int rightmostCount = dq.removeFirst().getValue();
// cost -= (long) (rightmostNum - nums[j--]);
// if (rightmostCount > 1)
// dq.offerFirst(new Pair<>(rightmostNum, rightmostCount - 1));
// }
// ans += j - i + 1;
// }
//
// return ans;
// }
// }
// Accepted solution for LeetCode #3420: Count Non-Decreasing Subarrays After K Operations
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #3420: Count Non-Decreasing Subarrays After K Operations
// class Solution {
// public long countNonDecreasingSubarrays(int[] nums, int k) {
// long ans = 0;
// long cost = 0;
// // Store (number, count) pairs in non-increasing order. The numbers in the
// // queue represent what nums[i..j] look like after adjustments.
// Deque<Pair<Integer, Integer>> dq = new ArrayDeque<>();
//
// for (int i = nums.length - 1, j = nums.length - 1; i >= 0; --i) {
// final int num = nums[i];
// int count = 1;
// while (!dq.isEmpty() && dq.getLast().getKey() < num) {
// final int nextNum = dq.getLast().getKey();
// final int nextCount = dq.removeLast().getValue();
// count += nextCount;
// // Adjust `nextNum`s to `num`.
// cost += (long) (num - nextNum) * nextCount;
// }
// dq.offerLast(new Pair<>(num, count));
// while (cost > k) {
// final int rightmostNum = dq.getFirst().getKey();
// final int rightmostCount = dq.removeFirst().getValue();
// cost -= (long) (rightmostNum - nums[j--]);
// if (rightmostCount > 1)
// dq.offerFirst(new Pair<>(rightmostNum, rightmostCount - 1));
// }
// ans += j - i + 1;
// }
//
// return ans;
// }
// }
Use this to step through a reusable interview workflow for this problem.
For each element, scan left (or right) to find the next greater/smaller element. The inner scan can visit up to n elements per outer iteration, giving O(n²) total comparisons. No extra space needed beyond loop variables.
Each element is pushed onto the stack at most once and popped at most once, giving 2n total operations = O(n). The stack itself holds at most n elements in the worst case. The key insight: amortized O(1) per element despite the inner while-loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Pushing without popping stale elements invalidates next-greater/next-smaller logic.
Usually fails on: Indices point to blocked elements and outputs shift.
Fix: Pop while invariant is violated before pushing current element.
Wrong move: Using `if` instead of `while` leaves the window invalid for multiple iterations.
Usually fails on: Over-limit windows stay invalid and produce wrong lengths/counts.
Fix: Shrink in a `while` loop until the invariant is valid again.