Count non decreasing subarrays after k operations

Array Stack Segment Tree Queue Sliding Window Monotonic Stack Monotonic Queue

23.8% acceptance

Feb 25, 2026

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

// O(n) sliding window with monotonic deque.
//
// Key insight: the minimum cost to make nums[l..r] non-decreasing by incrementing equals
//   sum_of_suffix_maxima(b[l..r]) - sum(b[l..r])
// where b = reversed(nums), and "suffix max" at position i = max(b[i..r]).
//
// Reversing preserves the COUNT of valid subarrays via bijection (l,r) <-> (n-1-r, n-1-l).
//
// We use a sliding window [left..r] on b with a (val, cnt) deque tracking sum_s =
// sum of max(b[i..r]) for each i in [left..r].  When adding b[r]: pop back entries
// with val <= b[r] (their max is now superseded by b[r]), accumulate their counts, push
// (b[r], total_cnt).  When cost = sum_s - window_psum > k: shrink from left by decrementing
// the front entry's count (and popping when 0).

impl Solution {
  pub fn count_non_decreasing_subarrays(nums: Vec<i32>, k: i32) -> i64 {
    use std::collections::VecDeque;
    let n = nums.len();
    let k = k as i64;

    // Reverse the array. Counting valid subarrays is invariant under reversal
    // (bijection (l,r) <-> (n-1-r, n-1-l)), and for the reversed array b the cost formula
    // sum_of_suffix_maxima(b[l..r]) - sum(b[l..r]) is amenable to a sliding window.
    let b: Vec<i64> = nums.into_iter().rev().map(|x| x as i64).collect();

    // Prefix sums of b
    let mut psum = vec![0i64; n + 1];
    for i in 0..n {
      psum[i + 1] = psum[i] + b[i];
    }

    // Deque of (val, count): sum_s = sum of max(b[i..r]) for i in [left..r].
    // When adding b[r]: merge back entries with val <= b[r] into one (b[r], merged_cnt).
    // When cost > k: shrink from front by decrementing front.count.
    let mut dq: VecDeque<(i64, usize)> = VecDeque::new();
    let mut sum_s = 0i64;
    let mut left = 0usize;
    let mut ans = 0i64;

    for r in 0..n {
      let mut cnt = 1usize;
      while let Some(&(v, c)) = dq.back() {
        if v <= b[r] {
          dq.pop_back();
          sum_s -= v * c as i64;
          cnt += c;
        } else {
          break;
        }
      }
      dq.push_back((b[r], cnt));
      sum_s += b[r] * cnt as i64;

      while sum_s - (psum[r + 1] - psum[left]) > k {
        let front = dq.front_mut().unwrap();
        sum_s -= front.0;
        front.1 -= 1;
        if front.1 == 0 {
          dq.pop_front();
        }
        left += 1;
      }

      ans += (r - left + 1) as i64;
    }
    ans
  }
}