Minimum Number of Removals to Make Mountain Array: LIS + LDS Pattern

Given an array of integers, you need to find the minimum number of elements to remove so the remaining array forms a mountain array. A mountain array strictly increases to a peak element, then strictly decreases. The peak cannot be the first or last element, and the array must have at least three elements.

This is LeetCode 1671: Minimum Number of Removals to Make Mountain Array, a hard problem that combines two classic DP ideas into one clean solution. Once you see the connection to Longest Increasing Subsequence, the whole approach falls into place.

Why this problem matters

Mountain array problems test whether you can decompose a complex structural constraint into simpler subproblems. The mountain shape, strictly increasing then strictly decreasing, looks intimidating at first. But the key realization is that you already know how to find the longest increasing subsequence from the left and the longest decreasing subsequence from the right. Those are the same computation, just run in opposite directions.

This problem also shows up as a building block in real-world scenarios. Any time you need to find the longest "up-then-down" pattern in a sequence (stock price peaks, signal processing, terrain analysis), the LIS + LDS combination is the tool you reach for.

If you have already solved Longest Increasing Subsequence, you have 80% of what you need here. The remaining 20% is recognizing that "longest mountain subsequence" is just LIS from the left plus LIS from the right, merged at each possible peak. That pattern recognition is what separates someone who solves individual problems from someone who sees the connections between them.

The key insight

Instead of trying to build the mountain directly, flip the problem. Ask: what is the longest mountain subsequence I can keep? Then the answer is n minus that length.

A mountain subsequence has a peak at some index i, with a strictly increasing sequence to the left of i and a strictly decreasing sequence to the right. For a fixed peak i, the longest mountain through that peak is:

• The longest increasing subsequence ending at i (call it LIS[i])
• Plus the longest decreasing subsequence starting at i (call it LDS[i])
• Minus 1, because the peak itself is counted in both

So the mountain length at peak i is LIS[i] + LDS[i] - 1. A valid peak requires LIS[i] >= 2 and LDS[i] >= 2 (there must be at least one element on each side).

Try every index as a potential peak, take the maximum mountain length, and subtract from n.

The solution

import bisect

def minimum_mountain_removals(nums):
    n = len(nums)

    lis = [0] * n
    tails = []
    for i in range(n):
        pos = bisect.bisect_left(tails, nums[i])
        if pos == len(tails):
            tails.append(nums[i])
        else:
            tails[pos] = nums[i]
        lis[i] = pos + 1

    lds = [0] * n
    tails = []
    for i in range(n - 1, -1, -1):
        pos = bisect.bisect_left(tails, nums[i])
        if pos == len(tails):
            tails.append(nums[i])
        else:
            tails[pos] = nums[i]
        lds[i] = pos + 1

    max_mountain = 0
    for i in range(1, n - 1):
        if lis[i] >= 2 and lds[i] >= 2:
            max_mountain = max(max_mountain, lis[i] + lds[i] - 1)

    return n - max_mountain

The solution has three phases. First, compute LIS[i] for every index by running the standard patience sorting algorithm left to right. For each element, binary search into a tails array to find where it belongs. The position plus one gives the length of the longest increasing subsequence ending at that index.

Second, compute LDS[i] for every index by running the exact same algorithm, but scanning right to left. This gives the longest decreasing subsequence starting at each index (equivalently, the longest increasing subsequence in the reversed suffix).

Third, iterate through every index that could be a valid peak (indices 1 through n - 2). A valid peak needs at least one increasing element before it and at least one decreasing element after it, so both LIS[i] and LDS[i] must be at least 2. Track the maximum mountain length, and return n minus that maximum.

Visual walkthrough

Let's trace through the full algorithm on nums = [2, 1, 1, 5, 6, 2, 3, 1]. We compute LIS from the left, LDS from the right, combine them at each valid peak, and find that the longest mountain subsequence has length 5.

The peak at index 4 (value 6) gives the best mountain. The increasing side reaches length 3 with subsequence [1, 5, 6], and the decreasing side reaches length 3 with subsequence [6, 3, 1]. Combined, that is a mountain of length 5. We remove 8 - 5 = 3 elements.

Complexity analysis

The time complexity is O(n log n) because we run the patience sorting algorithm twice (once left to right, once right to left), and each run processes n elements with an O(log n) binary search per element. The final peak-finding loop is O(n), which does not change the overall bound.

The space complexity is O(n) for the lis, lds, and tails arrays. The tails array is reused between the two passes, so it does not add extra space beyond O(n).

The building blocks

1. Longest Increasing Subsequence with binary search

tails = []
for i in range(n):
    pos = bisect.bisect_left(tails, nums[i])
    if pos == len(tails):
        tails.append(nums[i])
    else:
        tails[pos] = nums[i]
    lis[i] = pos + 1

This is the standard O(n log n) LIS algorithm using patience sorting. You maintain a tails array where tails[k] holds the smallest possible ending value for an increasing subsequence of length k + 1. For each element, a binary search finds where it fits. The same pattern appears in Longest Increasing Subsequence, Russian Doll Envelopes (LeetCode 354), and any problem that asks for the length of the longest sorted subsequence.

2. Bidirectional DP with peak merging

for i in range(1, n - 1):
    if lis[i] >= 2 and lds[i] >= 2:
        max_mountain = max(max_mountain, lis[i] + lds[i] - 1)

This is the technique of running a DP computation from both directions and merging the results at each position. You saw the same idea in the Candy problem (two-pass greedy) and Best Time to Buy and Sell Stock III (forward and backward DP). Any time an element depends on information from both the left prefix and the right suffix, computing two separate arrays and combining them is the standard approach.

Edge cases

• Array of length 3: the minimum valid mountain. If it is already a mountain (strictly increasing then decreasing), return 0. Otherwise, no valid mountain exists, but the problem guarantees a solution exists.
• Strictly increasing array: no valid peak exists because there is no decreasing side. The problem constraints guarantee the input has a valid mountain subsequence, but your code should handle this by checking LDS[i] >= 2.
• Strictly decreasing array: same issue in the other direction. Check LIS[i] >= 2.
• Plateau at the peak: values like [1, 3, 3, 2] do not form a valid mountain because the peak must be strictly greater than its neighbors. The strict inequality in bisect_left handles this correctly.
• Multiple valid peaks: the algorithm naturally handles this by trying every index as a potential peak and taking the maximum.
• All elements equal: no valid mountain exists. Every LIS[i] and LDS[i] equals 1, so no index qualifies as a peak.

From understanding to recall

You have just traced through the LIS + LDS mountain pattern from start to finish. The logic is clean: compute increasing subsequence lengths from both directions, merge at each peak, subtract from n. But writing it correctly in an interview requires remembering several details. You need to use bisect_left (not bisect_right) for strict increases. You need the validity check that both LIS[i] and LDS[i] are at least 2. And you need to exclude the first and last indices as peak candidates.

Spaced repetition locks these details into long-term memory. You practice writing the LIS binary search loop, the reverse-direction LDS pass, and the peak merge logic from scratch at increasing intervals. After a few reps, the mountain pattern is automatic. You see "minimize removals to form a shape" and the LIS + LDS decomposition is the first thing that comes to mind.

Related posts

• Longest Increasing Subsequence - The core LIS algorithm that powers half of this solution
• Jump Game II - Another greedy problem where you build optimal substructure across the array
• Best Time to Buy and Sell Stock III - Forward and backward DP merged at each position, the same bidirectional pattern used here

CodeBricks breaks the mountain array problem into its LIS binary search and bidirectional peak merging building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a mountain or LIS variant shows up in your interview, you do not think about it. You just write it.