Count stable subarrays

Array Binary Search Prefix Sum

32.2% acceptance

Feb 25, 2026

You are given an integer array nums. A subarray of nums is called stable if it contains no inversions, i.e., there is no pair of indices i < j such that nums[i] > nums[j]. You are also given a 2D integer array queries of length q, where each queries[i] = [li, ri] represents a query. For each query [li, ri], compute the number of stable subarrays that lie entirely within the segment nums[li..ri]. Return an integer array ans of length q, where ans[i] is the answer to the ith query. Note: A single element subarray is considered stable.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_stable_subarrays(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i64> {
    let n = nums.len();
    // reach[i] = end of non-decreasing run starting at i
    let mut reach = vec![0usize; n];
    reach[n - 1] = n - 1;
    for i in (0..n - 1).rev() {
      if nums[i] <= nums[i + 1] { reach[i] = reach[i + 1]; }
      else { reach[i] = i; }
    }
    // run_start[i] = start of run containing i
    let mut run_start = vec![0usize; n];
    run_start[0] = 0;
    for i in 1..n {
      if nums[i - 1] <= nums[i] { run_start[i] = run_start[i - 1]; }
      else { run_start[i] = i; }
    }
    // prefix[i] = sum_{j=0}^{i-1} (reach[j] - j + 1)
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n {
      prefix[i + 1] = prefix[i] + (reach[i] - i + 1) as i64;
    }
    queries.iter().map(|q| {
      let l = q[0] as usize;
      let r = q[1] as usize;
      let s = run_start[r];
      if s <= l {
        let len = (r - l + 1) as i64;
        len * (len + 1) / 2
      } else {
        let len = (r - s + 1) as i64;
        (prefix[s] - prefix[l]) + len * (len + 1) / 2
      }
    }).collect()
  }
}