Minimum number of removals to make mountain array

Array Binary Search Dynamic Programming Greedy

54.8% acceptance

Feb 25, 2026

2282

You may recall that an array arr is a mountain array if and only if: arr.length >= 3 There exists some index i with 0 < i < arr.length - 1 such that: arr[0] < arr[1] < ... < arr[i] > arr[i+1] > ... > arr[arr.length-1] Given nums, return the minimum number of elements to remove to make it a mountain array.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn minimum_mountain_removals(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    // LIS ending at each index (from left)
    let mut lis_l = vec![1usize; n];
    for i in 1..n {
      for j in 0..i {
        if nums[j] < nums[i] {
          lis_l[i] = lis_l[i].max(lis_l[j] + 1);
        }
      }
    }
    // LIS starting at each index (from right = LDS)
    let mut lis_r = vec![1usize; n];
    for i in (0..n - 1).rev() {
      for j in i + 1..n {
        if nums[j] < nums[i] {
          lis_r[i] = lis_r[i].max(lis_r[j] + 1);
        }
      }
    }
    // For each valid peak i (lis_l[i]>=2, lis_r[i]>=2):
    // mountain length = lis_l[i] + lis_r[i] - 1
    let mut max_mountain = 0;
    for i in 1..n - 1 {
      if lis_l[i] >= 2 && lis_r[i] >= 2 {
        max_mountain = max_mountain.max(lis_l[i] + lis_r[i] - 1);
      }
    }
    (n - max_mountain) as i32
  }
}