Count bowl subarrays

Array Stack Monotonic Stack

48.0% acceptance

Feb 25, 2026

183

You are given an integer array nums with distinct elements. A subarray nums[l...r] of nums is called a bowl if: The subarray has length at least 3. That is, r - l + 1 >= 3. The minimum of its two ends is strictly greater than the maximum of all elements in between. That is, min(nums[l], nums[r]) > max(nums[l + 1], ..., nums[r - 1]). Return the number of bowl subarrays in nums.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn bowl_subarrays(nums: Vec<i32>) -> i64 {
    let n = nums.len();
    if n < 3 { return 0; }

    // next_greater[i]: first j > i with nums[j] > nums[i], or n if none.
    // A bowl (l,r) needs nums[l] > all inner elements, which holds iff
    // next_greater[l] >= r (no element in (l, r) exceeds nums[l]).
    let mut next_greater = vec![n; n];
    {
      let mut stack: Vec<usize> = Vec::new();
      for i in 0..n {
        while let Some(&top) = stack.last() {
          if nums[i] > nums[top] {
            next_greater[top] = i;
            stack.pop();
          } else {
            break;
          }
        }
        stack.push(i);
      }
    }

    // prev_greater[i]: last j < i with nums[j] > nums[i], or n (sentinel) if none.
    // A bowl (l,r) needs nums[r] > all inner elements, which holds iff
    // prev_greater[r] <= l (no element in (l, r) exceeds nums[r]).
    let mut prev_greater = vec![n; n];
    {
      let mut stack: Vec<usize> = Vec::new();
      for i in 0..n {
        while let Some(&top) = stack.last() {
          if nums[top] < nums[i] {
            stack.pop();
          } else {
            break;
          }
        }
        prev_greater[i] = stack.last().copied().unwrap_or(n);
        stack.push(i);
      }
    }

    // Sweep r left→right. Maintain a Fenwick tree of "active" l positions.
    // l is active at r iff next_greater[l] >= r.
    // Deactivate l when r passes next_greater[l]: group by deactivate_after[v].
    // For each r, count active l in [prev_greater[r], r-2].
    // (prev_greater[r] <= l guarantees no inner element exceeds nums[r].)
    let mut deactivate_after: Vec<Vec<usize>> = vec![Vec::new(); n + 1];
    for l in 0..n {
      deactivate_after[next_greater[l]].push(l);
    }

    // Fenwick tree (BIT) for prefix sums over positions [0, n-1].
    let mut bit = vec![0i64; n + 1];
    macro_rules! bit_update {
      ($i:expr, $d:expr) => {{
        let mut i = $i + 1;
        while i <= n { bit[i] += $d; i += i & i.wrapping_neg(); }
      }};
    }
    macro_rules! bit_prefix {
      ($i:expr) => {{
        let mut s = 0i64;
        let mut i = $i + 1;
        while i > 0 { s += bit[i]; i -= i & i.wrapping_neg(); }
        s
      }};
    }

    for i in 0..n { bit_update!(i, 1); }

    let mut count = 0i64;
    for r in 2..n {
      // Deactivate all l where next_greater[l] = r-1 (now < r, so invalid).
      for &l in &deactivate_after[r - 1] {
        bit_update!(l, -1);
      }

      // Query: active l in [l_lo, r-2].
      let l_lo = if prev_greater[r] == n { 0 } else { prev_greater[r] };
      let l_hi = r - 2;
      if l_lo <= l_hi {
        count += if l_lo == 0 {
          bit_prefix!(l_hi)
        } else {
          bit_prefix!(l_hi) - bit_prefix!(l_lo - 1)
        };
      }
    }
    count
  }
}