{x}
blog image

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].

 

Constraints:

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

Solution Explanation: Minimum Number of Removals to Make Mountain Array

This problem asks for the minimum number of elements to remove from an array to make it a mountain array. A mountain array is defined as an array with at least three elements, strictly increasing to a peak, and then strictly decreasing.

The most efficient approach uses dynamic programming. We can break down the problem into two subproblems: finding the longest increasing subsequence (LIS) from the left and the longest decreasing subsequence (LDS) from the right.

Algorithm:

  1. Longest Increasing Subsequence (LIS) from the Left:

    • Create an array left of the same size as nums, initialized with all 1s. left[i] will store the length of the LIS ending at index i.
    • Iterate through nums from index 1. For each element nums[i], iterate through the elements before it (nums[j] where j < i). If nums[i] > nums[j], it means we can extend the LIS ending at j to include nums[i]. Update left[i] to be the maximum of its current value and left[j] + 1.

  2. Longest Decreasing Subsequence (LDS) from the Right:

    • Create an array right of the same size as nums, initialized with all 1s. right[i] will store the length of the LDS starting at index i.
    • Iterate through nums from the second to last element (n-2) down to 0. For each element nums[i], iterate through the elements after it (nums[j] where j > i). If nums[i] > nums[j], it means we can extend the LDS starting at j to include nums[i]. Update right[i] to be the maximum of its current value and right[j] + 1.

  3. Finding the Maximum Length Mountain:

    • Iterate through left and right. For each index i, if both left[i] > 1 and right[i] > 1, it indicates that we have found a potential peak at index i. The length of the mountain formed at index i is left[i] + right[i] - 1 (we subtract 1 because the peak is counted twice). Keep track of the maximum length of any mountain found.

  4. Calculating Minimum Removals:

    • The minimum number of removals is the total number of elements (n) minus the maximum length mountain found.

Time and Space Complexity:

  • Time Complexity: O(n^2) due to the nested loops in the LIS and LDS calculations.
  • Space Complexity: O(n) to store the left and right arrays.

Code Implementation (Python):

def minimumMountainRemovals(nums):
    n = len(nums)
    left = [1] * n
    right = [1] * n
 
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                left[i] = max(left[i], left[j] + 1)
 
    for i in range(n - 2, -1, -1):
        for j in range(i + 1, n):
            if nums[i] > nums[j]:
                right[i] = max(right[i], right[j] + 1)
 
    max_len = 0
    for i in range(n):
        if left[i] > 1 and right[i] > 1:
            max_len = max(max_len, left[i] + right[i] - 1)
 
    return n - max_len

The code in other languages (Java, C++, Go, TypeScript, Rust) provided in the original response follows the same algorithm and has equivalent time and space complexity. The only differences are syntax and standard library function calls specific to each language.