Maximum of minimum values in all subarrays

Array Stack Monotonic Stack

48.0% acceptance

Mar 31, 2026

146

You are given an integer array nums of size n. You are asked to solve n queries for each integer i in the range 0 <= i < n. To solve the ith query: Find the minimum value in each possible subarray of size i + 1 of the array nums. Find the maximum of those minimum values. This maximum is the answer to the query. Return a 0-indexed integer array ans of size n such that ans[i] is the answer to the ith query. A subarray is a contiguous sequence of elements in an array.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn find_maximums(nums: Vec<i32>) -> Vec<i32> {
    let n = nums.len();
    // For each element, find the range where it's the minimum using monotonic stack
    let mut left = vec![0i64; n]; // left[i] = index of previous smaller element + 1
    let mut right = vec![0i64; n]; // right[i] = index of next smaller element - 1
    let mut stack: Vec<usize> = Vec::new();
    
    for i in 0..n {
      while !stack.is_empty() && nums[*stack.last().unwrap()] >= nums[i] {
        stack.pop();
      }
      left[i] = if stack.is_empty() { -1 } else { *stack.last().unwrap() as i64 };
      stack.push(i);
    }
    
    stack.clear();
    for i in (0..n).rev() {
      while !stack.is_empty() && nums[*stack.last().unwrap()] >= nums[i] {
        stack.pop();
      }
      right[i] = if stack.is_empty() { n as i64 } else { *stack.last().unwrap() as i64 };
      stack.push(i);
    }
    
    // For each element nums[i], it's the minimum of all subarrays of size 1..=window
    // where window = right[i] - left[i] - 1
    // So ans[window-1] = max(ans[window-1], nums[i])
    let mut ans = vec![0i32; n];
    for i in 0..n {
      let window = (right[i] - left[i] - 1) as usize;
      ans[window - 1] = ans[window - 1].max(nums[i]);
    }
    
    // Fill in: ans[i] >= ans[i+1] (larger windows have smaller or equal max-of-mins)
    for i in (0..n - 1).rev() {
      ans[i] = ans[i].max(ans[i + 1]);
    }
    
    ans
  }
}