Maximum length of semi decreasing subarrays

Array Stack Sorting Monotonic Stack

70.1% acceptance

Mar 31, 2026

137

You are given an integer array nums. Return the length of the longest semi-decreasing subarray of nums, and 0 if there are no such subarrays. A subarray is a contiguous non-empty sequence of elements within an array. A non-empty array is semi-decreasing if its first element is strictly greater than its last element.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn max_subarray_length(nums: Vec<i32>) -> i32 {
    use std::collections::BTreeMap;
    let n = nums.len();
    // For each value, store the first (smallest) index
    let mut first_index: BTreeMap<i32, usize> = BTreeMap::new();
    let mut ans = 0i32;
    // We need first[i] > last[j] where nums[first_idx] > nums[last_idx]
    // Track minimum index seen for values strictly greater than current
    // Iterate right to left, for each position find earliest index of a strictly greater value
    let mut min_idx_stack: Vec<usize> = Vec::new(); // monotone stack of first occurrences by decreasing value
    // Build: group by value, store first index
    for i in 0..n {
      first_index.entry(nums[i]).or_insert(i);
    }
    // Collect (value, first_index) sorted by value descending
    let mut entries: Vec<(i32, usize)> = first_index.into_iter().collect();
    entries.sort_by(|a, b| b.0.cmp(&a.0));
    // Build monotone stack of first indices (non-increasing indices for decreasing values)
    // Actually, we want for each end position, the earliest start with greater value
    // Simpler approach: for each value, store first and last index
    let mut last_index = std::collections::BTreeMap::new();
    for i in 0..n {
      last_index.insert(nums[i], i); // overwrites to last
    }
    // Recollect first indices
    let mut first_idx_map = std::collections::BTreeMap::new();
    for i in 0..n {
      first_idx_map.entry(nums[i]).or_insert(i);
    }
    // For each value v (as potential end), find any value > v with first_index < last_index[v]
    // The length would be last_index[v] - first_index[w] + 1
    // We want to maximize this, so we want minimum first_index[w] for w > v
    // Build prefix min of first_index from highest value down
    let mut sorted_vals: Vec<i32> = first_idx_map.keys().cloned().collect();
    sorted_vals.sort();
    // min_first[i] = min first_index for values >= sorted_vals[i]
    let k = sorted_vals.len();
    let mut min_first = vec![usize::MAX; k + 1];
    for i in (0..k).rev() {
      min_first[i] = min_first[i + 1].min(*first_idx_map.get(&sorted_vals[i]).unwrap());
    }
    for i in 0..k {
      let v = sorted_vals[i];
      let last = *last_index.get(&v).unwrap();
      // Find min first_index for values strictly > v
      // Binary search for first value > v
      let pos = sorted_vals.partition_point(|&x| x <= v);
      if pos < k {
        let mf = min_first[pos];
        if mf < last {
          ans = ans.max((last - mf + 1) as i32);
        }
      }
    }
    ans
  }
}