Count subarrays with cost less than or equal to k

Array Queue Monotonic Queue

45.5% acceptance

Mar 16, 2026

148

You are given an integer array nums, and an integer k. For any subarray nums[l..r], define its cost as: cost = (max(nums[l..r]) - min(nums[l..r])) * (r - l + 1). Return an integer denoting the number of subarrays of nums whose cost is less than or equal to k.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_subarrays(nums: Vec<i32>, k: i64) -> i64 {
    // Sliding window with monotonic deques for min and max
    use std::collections::VecDeque;

    let n = nums.len();
    let mut max_deque: VecDeque<usize> = VecDeque::new(); // decreasing
    let mut min_deque: VecDeque<usize> = VecDeque::new(); // increasing
    let mut left = 0;
    let mut result: i64 = 0;

    for right in 0..n {
      // Maintain max deque (decreasing)
      while !max_deque.is_empty() && nums[*max_deque.back().unwrap()] <= nums[right] {
        max_deque.pop_back();
      }
      max_deque.push_back(right);

      // Maintain min deque (increasing)
      while !min_deque.is_empty() && nums[*min_deque.back().unwrap()] >= nums[right] {
        min_deque.pop_back();
      }
      min_deque.push_back(right);

      // Shrink window from left while cost > k
      while left <= right {
        let max_val = nums[*max_deque.front().unwrap()] as i64;
        let min_val = nums[*min_deque.front().unwrap()] as i64;
        let len = (right - left + 1) as i64;
        let cost = (max_val - min_val) * len;
        if cost <= k {
          break;
        }
        left += 1;
        if *max_deque.front().unwrap() < left {
          max_deque.pop_front();
        }
        if *min_deque.front().unwrap() < left {
          min_deque.pop_front();
        }
      }

      result += (right - left + 1) as i64;
    }

    result
  }
}