Minimum Number of Removals to Make Mountain Array

Minimum Number of Removals to Make Mountain Array

1. What is this problem about?

A "mountain array" is an array that strictly increases to a peak element and then strictly decreases. In this problem, you are given an array of integers and must determine the minimum number of elements to remove so that the remaining elements form a mountain array. The resulting mountain must have at least three elements: one peak and at least one element on either side.

2. Why is this asked in interviews?

This is a high-level optimization problem frequently asked by Google and Microsoft. It tests a candidate's ability to apply the Longest Increasing Subsequence (LIS) pattern in a non-trivial way. Instead of finding a single LIS, you must find two interdependent sequences that meet at a peak. This requires strong dynamic programming or binary search skills and the ability to handle edge cases, such as ensuring the mountain actually has two "sides."

3. Algorithmic pattern used

The core pattern is Longest Increasing Subsequence (LIS). Specifically, you calculate the LIS starting from the left for every index i, and the LIS starting from the right (which is the Longest Decreasing Subsequence) for every index i. The maximum mountain size at index i is LIS_left[i] + LDS_right[i] - 1, provided both sides have at least two elements (including the peak). The minimum removals is then total_length - max_mountain_size.

4. Example explanation

Consider the array: [2, 1, 1, 5, 6, 2, 3, 1].

• We want to find a peak. Let's look at index 4 (value 6).
• LIS from left ending at 6: [2, 5, 6] (length 3).
• LIS from right ending at 6 (decreasing): [6, 3, 1] or [6, 2, 1] (length 3).
• Mountain size: 3 + 3 - 1 = 5.
• Removals: 8 - 5 = 3. The algorithm iterates through all possible peaks to find the one that results in the largest mountain.

5. Common mistakes candidates make

A common error is forgetting the requirement that a mountain must have both an increasing and a decreasing part. If a candidate picks the very first or very last element as a "peak," the mountain is invalid. Another mistake is using a simple O(n²) LIS approach when the constraints require an O(n log n) solution using binary search (patience sorting).

6. Interview preparation tip

Practice the LIS pattern until you can implement it with binary search in your sleep. Once you master the base version, problems like "Mountain Array" or "Bitonic Subsequence" become much easier to visualize. Always double-check your peak conditions to ensure the mountain isn't just a simple increasing or decreasing line.