Minimum Number of Removals to Make Mountain Array

hard dp lis

Problem

You are given an integer array nums. A mountain array has at least 3 elements and climbs strictly up to a single peak, then falls strictly down — the peak cannot be the first or last element, and equal neighbours are not allowed on either slope. Return the minimum number of elements to delete so that the remaining array is a mountain (the input is guaranteed to allow one).

Constraints: 3 ≤ nums.length ≤ 1000 and 1 ≤ nums[i] ≤ 10⁹; deletions keep the relative order of the surviving elements, so we are really choosing a subsequence to keep.

Inputnums = [2,1,1,5,6,2,3,1]

Output3

Removing the elements at indices 0, 1 and 5 leaves [1,5,6,3,1], which rises strictly to 6 and then falls strictly.

nums (comma-separated)

def minimum_mountain_removals(nums):
    n = len(nums)
    lis = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                lis[i] = max(lis[i], lis[j] + 1)
    lds = [1] * n
    for i in range(n - 1, -1, -1):
        for j in range(i + 1, n):
            if nums[j] < nums[i]:
                lds[i] = max(lds[i], lds[j] + 1)
    best = 0
    for i in range(n):
        if lis[i] >= 2 and lds[i] >= 2:
            best = max(best, lis[i] + lds[i] - 1)
    return n - best

function minimumMountainRemovals(nums) {
  const n = nums.length;
  const lis = new Array(n).fill(1);
  for (let i = 0; i < n; i++)
    for (let j = 0; j < i; j++)
      if (nums[j] < nums[i]) lis[i] = Math.max(lis[i], lis[j] + 1);
  const lds = new Array(n).fill(1);
  for (let i = n - 1; i >= 0; i--)
    for (let j = i + 1; j < n; j++)
      if (nums[j] < nums[i]) lds[i] = Math.max(lds[i], lds[j] + 1);
  let best = 0;
  for (let i = 0; i < n; i++)
    if (lis[i] >= 2 && lds[i] >= 2)
      best = Math.max(best, lis[i] + lds[i] - 1);
  return n - best;
}

int minimumMountainRemovals(int[] nums) {
    int n = nums.length;
    int[] lis = new int[n], lds = new int[n];
    Arrays.fill(lis, 1);
    Arrays.fill(lds, 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            if (nums[j] < nums[i]) lis[i] = Math.max(lis[i], lis[j] + 1);
    for (int i = n - 1; i >= 0; i--)
        for (int j = i + 1; j < n; j++)
            if (nums[j] < nums[i]) lds[i] = Math.max(lds[i], lds[j] + 1);
    int best = 0;
    for (int i = 0; i < n; i++)
        if (lis[i] >= 2 && lds[i] >= 2)
            best = Math.max(best, lis[i] + lds[i] - 1);
    return n - best;
}

int minimumMountainRemovals(vector<int>& nums) {
    int n = nums.size();
    vector<int> lis(n, 1), lds(n, 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            if (nums[j] < nums[i]) lis[i] = max(lis[i], lis[j] + 1);
    for (int i = n - 1; i >= 0; i--)
        for (int j = i + 1; j < n; j++)
            if (nums[j] < nums[i]) lds[i] = max(lds[i], lds[j] + 1);
    int best = 0;
    for (int i = 0; i < n; i++)
        if (lis[i] >= 2 && lds[i] >= 2)
            best = max(best, lis[i] + lds[i] - 1);
    return n - best;
}

Explanation

Removing the fewest elements is the same as keeping the most. Whatever we keep must climb strictly and then fall strictly — a bitonic subsequence. So the answer is n − (longest bitonic subsequence), where both the climb and the fall contain at least one step.

The climb through any index i is exactly the classic longest increasing subsequence ending at i: lis[i] = 1 + max(lis[j]) over all j < i with nums[j] < nums[i]. Symmetrically, scanning from the right gives lds[i], the longest strictly decreasing run starting at i. Each table is an O(n²) double loop.

The two tables meet at the peak. If index i is the summit, we keep lis[i] + lds[i] − 1 elements (the peak is counted by both tables, hence the −1). The guard lis[i] ≥ 2 and lds[i] ≥ 2 is essential: a mountain must actually rise before the peak and fall after it, so an index with nothing smaller on one side can never be the summit.

For the default example [2,1,1,5,6,2,3,1], index 4 (value 6) has lis = 3 (via 1 → 5 → 6) and lds = 3 (via 6 → 2 → 1), so it keeps 3 + 3 − 1 = 5 elements — better than any other peak. The minimum number of removals is 8 − 5 = 3, e.g. leaving [1,5,6,2,1].

Each of the three passes touches every pair of indices at most once, so the total time is O(n²) and the two tables use O(n) extra space. (Both LIS tables can also be built in O(n log n) with patience sorting if n is large, but the peak-combining idea stays identical.)

Time: O(n²) Space: O(n)