# Minimum Number of Removals to Make Mountain Array
**Difficulty:** HARD
[External](https://leetcode.com/problems/minimum-number-of-removals-to-make-mountain-array)
Canonical: https://scaleengineer.com/dsa/problems/minimum-number-of-removals-to-make-mountain-array
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming), [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [PayPal](https://scaleengineer.com/companies/paypal)
---
## Problem
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`.

# Approaches
## Dynamic Programming
This approach uses dynamic programming to solve the problem. The core idea is to rephrase the problem from finding the minimum number of removals to finding the maximum length of a subsequence that forms a mountain array. If the longest mountain subsequence has length `L`, then the minimum number of removals is `n - L`, where `n` is the length of the original array.
**Time:** O(n^2), where n is the number of elements in `nums`. Calculating the `lis` array takes O(n^2), and calculating the `lds` array also takes O(n^2). The final loop to find the maximum mountain length takes O(n). Thus, the total time complexity is dominated by the O(n^2) computations. · **Space:** O(n), where n is the number of elements in the input array. We use two additional arrays, `lis` and `lds`, each of size `n`.
**Pros:** The logic is a straightforward extension of the classic Longest Increasing Subsequence problem.; It's relatively easy to understand and implement.
**Cons:** The O(n^2) time complexity can be too slow for larger input sizes, although it passes for the given constraints.
### Explanation
A mountain array has a single peak. We can iterate through every element `nums[i]` and treat it as the peak of a potential mountain subsequence. For `nums[i]` to be a valid peak, there must be a strictly increasing subsequence ending at `nums[i]` and a strictly decreasing subsequence starting from `nums[i]`. The length of such a mountain subsequence would be the sum of the lengths of these two subsequences, minus one (since the peak is counted in both).

We can compute the lengths of these subsequences using dynamic programming:

1.  **Longest Increasing Subsequence (LIS) from the left:** We create an array `lis` where `lis[i]` stores the length of the longest increasing subsequence of `nums` that ends at index `i`. We can compute this in O(n^2) time.

2.  **Longest Decreasing Subsequence (LDS) from the right:** Similarly, we create an array `lds` where `lds[i]` stores the length of the longest decreasing subsequence of `nums` that starts at index `i`. This is equivalent to finding the LIS from right to left. This also takes O(n^2) time.

After computing both `lis` and `lds` arrays, we iterate through each index `i` from `0` to `n-1`. For each `i`, if `lis[i] > 1` and `lds[i] > 1` (which ensures that there's at least one element on the increasing slope and one on the decreasing slope), we consider `nums[i]` as a potential peak. The length of the mountain array with this peak is `lis[i] + lds[i] - 1`. We find the maximum possible length over all valid peaks.

Finally, the minimum number of removals is the total number of elements `n` minus this maximum length.

```java
import java.util.Arrays;

class Solution {
    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length;
        int[] lis = new int[n];
        int[] lds = new int[n];
        Arrays.fill(lis, 1);
        Arrays.fill(lds, 1);

        // Calculate LIS lengths from left to right
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    lis[i] = Math.max(lis[i], lis[j] + 1);
                }
            }
        }

        // Calculate LDS lengths (as LIS from right to left)
        for (int i = n - 2; i >= 0; i--) {
            for (int j = n - 1; j > i; j--) {
                if (nums[i] > nums[j]) {
                    lds[i] = Math.max(lds[i], lds[j] + 1);
                }
            }
        }

        int maxLength = 0;
        for (int i = 0; i < n; i++) {
            // A valid mountain peak must have both a left and a right side.
            if (lis[i] > 1 && lds[i] > 1) {
                maxLength = Math.max(maxLength, lis[i] + lds[i] - 1);
            }
        }

        return n - maxLength;
    }
}
```
### Algorithm
- The problem of finding the minimum number of removals is equivalent to finding the length of the longest subsequence that is a mountain array.
- We can iterate through each element `nums[i]` and consider it as the potential peak of a mountain subsequence.
- For each potential peak `nums[i]`, we need to find the length of the Longest Increasing Subsequence (LIS) ending at `i` and the length of the Longest Decreasing Subsequence (LDS) starting at `i`.
- The length of the mountain with peak `nums[i]` is `length(LIS) + length(LDS) - 1`.
- We can use dynamic programming to find these lengths.
  1.  Create an array `lis` of size `n`. `lis[i]` will store the length of the LIS ending at index `i`.
  2.  Calculate `lis` by iterating from left to right. For each `i`, `lis[i] = 1 + max(lis[j])` for all `j < i` where `nums[j] < nums[i]`.
  3.  Create an array `lds` of size `n`. `lds[i]` will store the length of the LDS starting at index `i`.
  4.  Calculate `lds` by iterating from right to left. For each `i`, `lds[i] = 1 + max(lds[j])` for all `j > i` where `nums[j] < nums[i]`.
  5.  Iterate through all possible peaks `i`. If `lis[i] > 1` and `lds[i] > 1` (to ensure both slopes exist), calculate the mountain length `lis[i] + lds[i] - 1` and find the maximum among all valid peaks.
  6.  The result is `n - maxLength`.

## Optimized DP with Binary Search
This approach enhances the previous dynamic programming solution by using a more efficient algorithm to compute the Longest Increasing Subsequence (LIS) and Longest Decreasing Subsequence (LDS) arrays. By leveraging binary search, we can reduce the time complexity for calculating these arrays from O(n^2) to O(n log n), leading to a more performant overall solution.
**Time:** O(n log n). Calculating the `lis` array involves a loop of `n` iterations, with a binary search (log n) inside, taking O(n log n). The same applies to calculating the `lds` array. The final loop is O(n). The total complexity is O(n log n). · **Space:** O(n), where n is the number of elements. We use `lis` and `lds` arrays of size `n`, and the `tails` list which can grow up to size `n`.
**Pros:** Highly efficient with O(n log n) time complexity.; Optimal solution for this problem under typical competitive programming constraints.
**Cons:** The implementation is more complex than the O(n^2) DP approach.; The logic behind the O(n log n) LIS calculation can be non-trivial to grasp.
### Explanation
The fundamental idea is identical to the first approach: find the length of the longest mountain subsequence by considering each element as a potential peak. The length of a mountain with peak `nums[i]` is `lis[i] + lds[i] - 1`.

The optimization lies in how we compute the `lis` and `lds` arrays. The standard O(n^2) LIS algorithm can be improved to O(n log n).

**Algorithm for O(n log n) LIS/LDS:**

1.  **Calculate `lis` array (LIS from left):**
    - We'll use an auxiliary list, `tails`, which will store the smallest tail of all increasing subsequences of a certain length. This list is always sorted.
    - We iterate through `nums` from left to right. For each `nums[i]`, we find the position to insert it into `tails` to maintain sorted order using binary search. Let this position be `idx`.
    - If `idx` is at the end of `tails`, we append `nums[i]`. Otherwise, we replace the element at `tails[idx]` with `nums[i]`. This step ensures that for a given subsequence length, we keep the one with the smallest possible tail, which gives a better chance for extension later.
    - The length of the LIS ending at `nums[i]` is `idx + 1`. We store this in `lis[i]`.

2.  **Calculate `lds` array (LIS from right):**
    - We apply the exact same logic, but we iterate through `nums` from right to left (`i = n-1` down to `0`). This calculates the length of the LIS ending at `i` considering elements to its right, which is precisely the length of the LDS starting at `i` that we need. We store this in `lds[i]`.

3.  **Find Longest Mountain:**
    - With the `lis` and `lds` arrays computed, we iterate through them. For any index `i` where `lis[i] > 1` and `lds[i] > 1`, we calculate the potential mountain length `lis[i] + lds[i] - 1` and update our `maxLength`.

4.  **Final Result:**
    - The minimum removals required is `n - maxLength`.

```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 = new int[n];
        List<Integer> tails = new ArrayList<>();

        // Calculate LIS from left to right
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            int idx = Collections.binarySearch(tails, num);
            if (idx < 0) {
                idx = -(idx + 1);
            }

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

        int[] lds = new int[n];
        tails.clear();

        // Calculate LIS from right to left (which is LDS)
        for (int i = n - 1; i >= 0; i--) {
            int num = nums[i];
            int idx = Collections.binarySearch(tails, num);
            if (idx < 0) {
                idx = -(idx + 1);
            }

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

        int maxLength = 0;
        for (int i = 0; i < n; i++) {
            if (lis[i] > 1 && lds[i] > 1) {
                maxLength = Math.max(maxLength, lis[i] + lds[i] - 1);
            }
        }

        return n - maxLength;
    }
}
```
### Algorithm
- This approach follows the same high-level strategy as the O(n^2) DP solution: find the longest mountain subsequence by checking every possible peak.
- The improvement comes from optimizing the calculation of the LIS and LDS arrays from O(n^2) to O(n log n).
- **Optimized LIS/LDS Calculation**:
  1.  To compute `lis[i]` (length of LIS ending at `i`), we maintain a sorted list, `tails`, representing the smallest tail of all increasing subsequences of a given length.
  2.  For each `num` in `nums`, we use binary search on `tails` to find its place. This tells us the length of the LIS ending with `num`.
  3.  We perform this process once from left to right to compute the `lis` array.
  4.  We repeat the process from right to left to compute the `lds` array.
  5.  The rest of the logic (finding the max length and the result) remains the same as the previous approach.

# Solutions
### Java

```java
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);
    for (int i = 1; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        if (nums[i] > nums[j]) {
          left[i] = Math.max(left[i], left[j] + 1);
        }
      }
    }
    for (int i = n - 2; i >= 0; --i) {
      for (int j = i + 1; j < n; ++j) {
        if (nums[i] > nums[j]) {
          right[i] = Math.max(right[i], right[j] + 1);
        }
      }
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      if (left[i] > 1 && right[i] > 1) {
        ans = Math.max(ans, left[i] + right[i] - 1);
      }
    }
    return n - ans;
  }
}

```

### CPP

```cpp
class Solution { public: int minimumMountainRemovals ( vector < int >& nums ) { int n = nums . size (); vector < int > left ( n , 1 ), right ( n , 1 ); for ( int i = 1 ; i < n ; ++ i ) { for ( int j = 0 ; j < i ; ++ j ) { if ( nums [ i ] > nums [ j ]) { left [ i ] = max ( left [ i ], left [ j ] + 1 ); } } } for ( int i = n - 2 ; i >= 0 ; -- i ) { for ( int j = i + 1 ; j < n ; ++ j ) { if ( nums [ i ] > nums [ j ]) { right [ i ] = max ( right [ i ], right [ j ] + 1 ); } } } int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( left [ i ] > 1 && right [ i ] > 1 ) { ans = max ( ans , left [ i ] + right [ i ] - 1 ); } } return n - ans ; } };
```

### Python

```python
class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int: 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) return n - max(a + b - 1 for a, b in zip(left, right) if a > 1 and b > 1)

```