Pseudo-code:

text
function solve_naive(nums):
    max_len = 0
    for each subsequence in getAllSubsequences(nums):
        if isMountain(subsequence):
            max_len = max(max_len, length(subsequence))
    return length(nums) - max_len

Complexity Analysis: The time complexity is $O(N \cdot 2^N)$. With $N$ up to 1000, $2^{1000}$ is astronomically large, causing an immediate Time Limit Exceeded (TLE). We need a polynomial time solution, specifically utilizing dynamic programming.

Core Insight for Minimum Number of Removals to Make Mountain Array

The key intuition for solving LeetCode 1671 is to decompose the mountain structure around its peak. If we fix an index i as the peak of the mountain, the problem splits into two independent subproblems:

1. Find the longest strictly increasing subsequence ending at index i (the left slope).
2. Find the longest strictly decreasing subsequence starting at index i (the right slope).

Since the right slope must be decreasing, finding a decreasing subsequence starting at i is equivalent to finding an increasing subsequence ending at i if we were to traverse the array backwards.

Therefore, we can precompute the LIS length ending at every index for both the forward direction and the backward direction.

Key Invariant: For any index i to be a valid peak, both the left slope (LIS ending at i) and the right slope (LDS starting at i) must have a length greater than 1. This ensures the peak is not the first or last element of the subsequence, satisfying the constraint 0 < i < arr.length - 1 relative to the subsequence indices.

Visual Description: Imagine calculating two arrays, left_dp and right_dp.

• left_dp[i] represents the height of the increasing steps leading up to index i.
• right_dp[i] represents the height of the increasing steps leading up to index i from the right side (reverse view).
• By overlapping these two arrays, for any index i, the total length of the mountain with peak i is left_dp[i] + right_dp[i] - 1 (we subtract 1 because the peak element at i is counted in both sequences).

Execution Flow

Let's trace the algorithm with nums = [2, 1, 1, 5, 6, 2, 3, 1].

1. Initialize: n = 8. Arrays lis and lds of size 8.

2. Calculate LIS (Left to Right):

   • We compute the LIS ending at each index.
   • lis becomes [1, 1, 1, 2, 3, 2, 3, 1].
   • Example: At index 4 (value 6), the sequence is [1, 5, 6], length 3.

3. Calculate LDS (Right to Left):

   • We compute LIS on the reversed array or look from right to left.
   • lds becomes [1, 3, 2, 3, 3, 2, 2, 1].
   • Example: At index 4 (value 6), looking right, the sequence is [6, 3, 1] or [6, 2, 1], length 3.

4. Identify Peaks:

   • Iterate i from 0 to 7. Check condition lis[i] > 1 && lds[i] > 1.
   • i=3 (val 5): lis=2, lds=3. Valid. Length = $2+3-1 = 4$.
   • i=4 (val 6): lis=3, lds=3. Valid. Length = .

5. Result:

   • Max mountain length is 5 (e.g., [1, 5, 6, 3, 1]).
   • Minimum removals = 8 - 5 = 3.

Proof of Correctness

The correctness relies on the Optimal Substructure property of the Longest Increasing Subsequence problem.

1. lis[i] correctly computes the maximum length of an increasing chain ending at i by definition.
2. lds[i] correctly computes the maximum length of a decreasing chain starting at i.
3. Since a mountain array is strictly defined as an increasing chain ending at i followed immediately by a decreasing chain starting at i, the longest mountain with peak i must be the concatenation of these two optimal subsequences.
4. By iterating over all possible peaks i, we guarantee finding the global maximum mountain length.

Reference Implementation

C++ Solution for LeetCode 1671

cpp
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int minimumMountainRemovals(vector<int>& nums) {
        int n = nums.size();
        
        // Helper to compute LIS lengths for every index
        auto get_lis_lengths = [&](const vector<int>& arr) {
            vector<int> lengths(arr.size(), 1);
            vector<int> tails; // Stores the smallest tail of all increasing subsequences of length i+1
            
            for (int i = 0; i < arr.size(); ++i) {
                int x = arr[i];
                // Binary search for the first element >= x
                auto it = lower_bound(tails.begin(), tails.end(), x);
                
                if (it == tails.end()) {
                    tails.push_back(x);
                    lengths[i] = tails.size();
                } else {
                    *it = x;
                    // The length ending at this index is the index in tails + 1
                    lengths[i] = distance(tails.begin(), it) + 1;
                }
            }
            return lengths;
        };

        // 1. Compute LIS ending at each index (Left to Right)
        vector<int> lis = get_lis_lengths(nums);

        // 2. Compute LDS starting at each index (Right to Left)
        // We reverse the array, compute LIS, then reverse the result back
        vector<int> reversed_nums = nums;
        reverse(reversed_nums.begin(), reversed_nums.end());
        vector<int> lds = get_lis_lengths(reversed_nums);
        reverse(lds.begin(), lds.end());

        int max_mountain = 0;

        // 3. Find the peak that maximizes mountain length
        for (int i = 1; i < n - 1; ++i) {
            // A valid peak must have both left and right slopes > 1
            if (lis[i] > 1 && lds[i] > 1) {
                max_mountain = max(max_mountain, lis[i] + lds[i] - 1);
            }
        }

        return n - max_mountain;
    }
};

Java Solution for LeetCode 1671

java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length;
        int[] lis = getLisLengths(nums);
        
        // Create reversed array for LDS
        int[] reversedNums = new int[n];
        for (int i = 0; i < n; i++) {
            reversedNums[i] = nums[n - 1 - i];
        }
        
        int[] ldsReversed = getLisLengths(reversedNums);
        // Correct the order of LDS to match original indices
        int[] lds = new int[n];
        for (int i = 0; i < n; i++) {
            lds[i] = ldsReversed[n - 1 - i];
        }

        int maxMountain = 0;

        // Iterate through potential peaks
        for (int i = 1; i < n - 1; i++) {
            // Valid peak check
            if (lis[i] > 1 && lds[i] > 1) {
                maxMountain = Math.max(maxMountain, lis[i] + lds[i] - 1);
            }
        }

        return n - maxMountain;
    }

    // Helper to compute LIS lengths ending at each index
    private int[] getLisLengths(int[] arr) {
        int n = arr.length;
        int[] lengths = new int[n];
        List<Integer> tails = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            int x = arr[i];
            // Binary search for insertion point
            int idx = Collections.binarySearch(tails, x);
            
            if (idx < 0) {
                idx = -(idx + 1); // Convert to insertion point
            }

            if (idx == tails.size()) {
                tails.add(x);
            } else {
                tails.set(idx, x);
            }
            lengths[i] = idx + 1;
        }
        return lengths;
    }
}

Python Solution for LeetCode 1671

python
import bisect

class Solution:
    def minimumMountainRemovals(self, nums: list[int]) -> int:
        n = len(nums)
        
        def get_lis_lengths(arr):
            lengths = [1] * len(arr)
            tails = [] # Stores smallest tail of all increasing subsequences
            
            for i, x in enumerate(arr):
                # Find the first element in tails >= x
                idx = bisect.bisect_left(tails, x)
                
                if idx < len(tails):
                    tails[idx] = x
                else:
                    tails.append(x)
                
                # The length of LIS ending at current element x is idx + 1
                lengths[i] = idx + 1
            return lengths

        # 1. Compute LIS from left to right
        lis = get_lis_lengths(nums)
        
        # 2. Compute LDS (LIS of reversed array)
        lds = get_lis_lengths(nums[::-1])[::-1]
        
        max_mountain = 0
        
        # 3. Find max mountain length
        for i in range(1, n - 1):
            if lis[i] > 1 and lds[i] > 1:
                max_mountain = max(max_mountain, lis[i] + lds[i] - 1)
                
        return n - max_mountain

Mastering the "peak" decomposition used here also applies to other "Bitonic" sequence problems.