Find the number of subarrays where boundary elements are maximum

Array Binary Search Stack Monotonic Stack

32.8% acceptance

Feb 23, 2026

262

You are given an array of positive integers nums. Return the number of subarrays of nums, where the first and the last elements of the subarray are equal to the largest element in the subarray.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_subarrays(nums: Vec<i32>) -> i64 {
    // Monotone stack: (value, count) in non-decreasing order from bottom to top
    // For each right endpoint i, count the valid left endpoints using the stack.
    let mut result: i64 = 0;
    let mut stack: Vec<(i32, i64)> = Vec::new(); // (value, count)

    for &x in &nums {
      // Pop elements smaller than x (they can't be the max of a subarray ending at i)
      while stack.last().map_or(false, |&(v, _)| v < x) {
        stack.pop();
      }
      result += 1; // single element subarray [i..=i]
      if stack.last().map_or(false, |&(v, _)| v == x) {
        let cnt = stack.last().unwrap().1;
        result += cnt;
        stack.last_mut().unwrap().1 += 1;
      } else {
        stack.push((x, 1));
      }
    }
    result
  }
}