Number of valid subarrays

Array Stack Monotonic Stack

79.9% acceptance

Mar 31, 2026

335

Given an integer array nums, return the number of non-empty subarrays with the leftmost element of the subarray not larger than other elements in the subarray. A subarray is a contiguous part of an array.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn valid_subarrays(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut stack: Vec<usize> = Vec::new();
    let mut result = 0i32;
    for i in 0..n {
      while let Some(&top) = stack.last() {
        if nums[i] < nums[top] {
          stack.pop();
          result += (i - top) as i32;
        } else {
          break;
        }
      }
      stack.push(i);
    }
    while let Some(top) = stack.pop() {
      result += (n - top) as i32;
    }
    result
  }
}