Code Implementation

class Solution:
    def minimumMountainRemovals(self, nums):
        n = len(nums)
        # Compute LIS from left to right
        left = [1] * n
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    left[i] = max(left[i], left[j] + 1)
        # Compute LIS from right to left (for decreasing part)
        right = [1] * n
        for i in range(n-1, -1, -1):
            for j in range(n-1, i, -1):
                if nums[j] < nums[i]:
                    right[i] = max(right[i], right[j] + 1)
        res = n
        for i in range(1, n-1):
            if left[i] > 1 and right[i] > 1:
                res = min(res, n - (left[i] + right[i] - 1))
        return res
      

class Solution {
public:
    int minimumMountainRemovals(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n, 1), right(n, 1);
        // LIS from left
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    left[i] = max(left[i], left[j] + 1);
                }
            }
        }
        // LIS from right (for decreasing part)
        for (int i = n-1; i >= 0; --i) {
            for (int j = n-1; j > i; --j) {
                if (nums[j] < nums[i]) {
                    right[i] = max(right[i], right[j] + 1);
                }
            }
        }
        int res = n;
        for (int i = 1; i < n-1; ++i) {
            if (left[i] > 1 && right[i] > 1) {
                res = min(res, n - (left[i] + right[i] - 1));
            }
        }
        return res;
    }
};
      

class Solution {
    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
        // LIS from left
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    left[i] = Math.max(left[i], left[j] + 1);
                }
            }
        }
        // LIS from right (for decreasing part)
        for (int i = n-1; i >= 0; i--) {
            for (int j = n-1; j > i; j--) {
                if (nums[j] < nums[i]) {
                    right[i] = Math.max(right[i], right[j] + 1);
                }
            }
        }
        int res = n;
        for (int i = 1; i < n-1; i++) {
            if (left[i] > 1 && right[i] > 1) {
                res = Math.min(res, n - (left[i] + right[i] - 1));
            }
        }
        return res;
    }
}
      

var minimumMountainRemovals = function(nums) {
    let n = nums.length;
    let left = new Array(n).fill(1);
    let right = new Array(n).fill(1);
    // LIS from left
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                left[i] = Math.max(left[i], left[j] + 1);
            }
        }
    }
    // LIS from right (for decreasing part)
    for (let i = n-1; i >= 0; i--) {
        for (let j = n-1; j > i; j--) {
            if (nums[j] < nums[i]) {
                right[i] = Math.max(right[i], right[j] + 1);
            }
        }
    }
    let res = n;
    for (let i = 1; i < n-1; i++) {
        if (left[i] > 1 && right[i] > 1) {
            res = Math.min(res, n - (left[i] + right[i] - 1));
        }
    }
    return res;
};
      

Problem Description

You are given an array of integers called nums. Your task is to remove the minimum number of elements from nums so that the resulting array is a mountain array.

A mountain array must satisfy:

• It has at least three elements.
• There exists some index i (with 0 < i < nums.length - 1) such that:
  • nums[0] < nums[1] < ... < nums[i]
  • nums[i] > nums[i+1] > ... > nums[nums.length - 1]

The goal is to find the minimum number of removals needed to make nums a mountain array.

Constraints:

• There is always at least one valid solution.
• Each element can be used at most once; do not reuse or duplicate elements.

Thought Process

At first glance, this problem might seem like it requires trying all possible combinations of removals to form a mountain array. However, this brute-force approach would be extremely slow for larger arrays.

Let's think about the structure of a mountain array. It consists of a strictly increasing sequence up to a peak, and then a strictly decreasing sequence after the peak. So, to form a mountain, we want to maximize the length of such a sequence, minimizing the number of removals.

The key insight is that for each possible peak position, we can compute:

• The length of the longest increasing subsequence (LIS) ending at that position (from the left).
• The length of the longest decreasing subsequence (LDS) starting from that position (from the right).

By finding the peak that gives the longest possible mountain, we can deduce the minimum removals as nums.length - mountain_length.

Solution Approach

Let's break down the solution step by step:

1. Compute the Longest Increasing Subsequence (LIS) for each index:
   • For each position i, find the length of the longest strictly increasing subsequence ending at i.
   • This can be done with dynamic programming: for each i, check all j < i and if nums[j] < nums[i], update LIS[i].
2. Compute the Longest Decreasing Subsequence (LDS) for each index:
   • This is similar to LIS, but from the right: for each position i, compute the length of the longest strictly decreasing subsequence starting from i.
   • Again, use dynamic programming, but iterate from the end to the start.
3. Find the maximum mountain length:
   • For each possible peak i (excluding the ends), if LIS[i] > 1 and LDS[i] > 1, the mountain at i has length LIS[i] + LDS[i] - 1 (subtract 1 to avoid double-counting the peak).
   • Keep track of the largest such mountain length.
4. Calculate the minimum removals:
   • Subtract the maximum mountain length from nums.length to get the answer.

We use arrays to store the LIS and LDS for efficiency, and dynamic programming ensures we don't recompute results.

Example Walkthrough

Let's walk through an example: nums = [2,1,1,5,6,2,3,1]

1. Compute LIS:
   • At each index, store the length of the longest increasing subsequence ending there.
   • For example: LIS = [1,1,1,2,3,2,3,1]
   • Explanation:
     • Index 0: 2 → length 1
     • Index 3: 5 (can come after 2 or 1) → length 2
     • Index 4: 6 (can come after 5) → length 3
     • Index 6: 3 (can come after 2 or 1) → length 3 (via 2,5 or 2,3)
2. Compute LDS (from the right):
   • For example: LDS = [2,1,1,3,3,2,2,1]
   • Explanation:
     • Index 3: 5 (after it, 2 and 1 are smaller) → length 3
     • Index 4: 6 (after it, 2, 3, 1 are smaller) → length 3
3. Find the best peak:
   • Check indices where both LIS and LDS are greater than 1 (not at the ends).
   • At index 4 (6): LIS=3, LDS=3 → mountain length = 3+3-1=5
   • At index 3 (5): LIS=2, LDS=3 → mountain length = 2+3-1=4
   • At index 6 (3): LIS=3, LDS=2 → mountain length = 3+2-1=4
   • The maximum is 5 (at index 4).
4. Compute removals:
   • Array length is 8, mountain length is 5, so answer is 8 - 5 = 3.

Time and Space Complexity

Brute-force approach:

• Would involve checking all possible subsets, which is exponential in time (O(2ⁿ)) and not feasible for large arrays.

• For each index, we may look at all prior (or later) indices, so both LIS and LDS computations are O(n²).
• Overall time complexity: O(n²).
• Space complexity: O(n) for storing the LIS and LDS arrays.

There are further optimizations using binary search to compute LIS in O(n log n), but the above solution is sufficient for most constraints.

Summary

To solve the "Minimum Number of Removals to Make Mountain Array" problem, we:

• Recognize the mountain array structure as a combination of an increasing and then decreasing subsequence.
• Use dynamic programming to compute the longest increasing and decreasing subsequences at every index.
• Find the peak that forms the largest possible mountain, minimizing removals.
• Subtract the mountain length from the array length to get the answer.