1671. Minimum Number of Removals to Make Mountain Array

You may recall that an array arr is a mountain array if and only if:

  • arr.length >= 3
  • There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that:
    • arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
    • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an integer array nums​​​, return the minimum number of elements to remove to make nums​​​ a mountain array.

 

Example 1:

Input: nums = [1,3,1]
Output: 0
Explanation: The array itself is a mountain array so we do not need to remove any elements.

Example 2:

Input: nums = [2,1,1,5,6,2,3,1]
Output: 3
Explanation: One solution is to remove the elements at indices 0, 1, and 5, making the array nums = [1,5,6,3,1].

Example 3:

Input: nums = [4,3,2,1,1,2,3,1]
Output: 4

Example 4:

Input: nums = [1,2,3,4,4,3,2,1]
Output: 1

 

Constraints:

  • 3 <= nums.length <= 1000
  • 1 <= nums[i] <= 109
  • It is guaranteed that you can make a mountain array out of nums.

Rust Solution

struct Solution;

impl Solution {
    fn minimum_mountain_removals(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut left = vec![0; n];
        let mut dp: Vec<i32> = vec![];
        for i in 0..n {
            let x = nums[i];
            let size = match dp.binary_search(&x) {
                Ok(j) => j + 1,
                Err(j) => {
                    if j == dp.len() {
                        dp.push(x);
                    } else {
                        dp[j] = x;
                    }
                    j + 1
                }
            };
            left[i] = size;
        }

        let mut right = vec![0; n];
        let mut dp: Vec<i32> = vec![];
        for i in (0..n).rev() {
            let x = nums[i];
            let size = match dp.binary_search(&x) {
                Ok(j) => j + 1,
                Err(j) => {
                    if j == dp.len() {
                        dp.push(x);
                    } else {
                        dp[j] = x;
                    }
                    j + 1
                }
            };
            right[i] = size;
        }

        let mut res = n;
        for i in 0..n {
            if left[i] != 1 && right[i] != 1 {
                res = res.min(n - (left[i] + right[i] - 1));
            }
        }
        res as i32
    }
}

#[test]
fn test() {
    let nums = vec![1, 3, 1];
    let res = 0;
    assert_eq!(Solution::minimum_mountain_removals(nums), res);
    let nums = vec![2, 1, 1, 5, 6, 2, 3, 1];
    let res = 3;
    assert_eq!(Solution::minimum_mountain_removals(nums), res);
    let nums = vec![4, 3, 2, 1, 1, 2, 3, 1];
    let res = 4;
    assert_eq!(Solution::minimum_mountain_removals(nums), res);
    let nums = vec![1, 2, 3, 4, 4, 3, 2, 1];
    let res = 1;
    assert_eq!(Solution::minimum_mountain_removals(nums), res);
}

Having problems with this solution? Click here to submit an issue on github.