Minimum Number of Removals to Make Mountain Array

Hard
1621.

Minimum Number of Removals to Make Mountain Array

Minimum Number of Removals to Make Mountain Array is a hard coding problem on arrays, dynamic programming and greedy, asked in Amazon, Google and Microsoft interviews.

An array arr is a mountain when arr.length >= 3 and there is a peak index i with 0 < i < arr.length - 1 such that the values strictly increase up to the peak and strictly decrease after it:

  • arr[0] < arr[1] < ... < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an array nums, return the fewest elements you must delete (keeping the others in order) so that what remains is a mountain. The input is guaranteed to allow a mountain.

Example 1

Input
nums = [1,3,1]
Output
0
Explanation
It is already a mountain.

Example 2

Input
nums = [2,1,1,5,6,2,3,1]
Output
3
Explanation
Delete indices 0, 1 and 5 to keep [1,5,6,3,1].

Example 3

Input
nums = [4,3,2,1,1,2,3,1]
Output
4
Explanation
Keep [1,2,3,1]; no five elements form a mountain.

Constraints

  • 3 <= nums.length <= 1000
  • 1 <= nums[i] <= 10^9
  • a mountain can always be made from nums
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumMountainRemovals = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Number of Removals to Make Mountain Array — Solution

Minimum Number of Removals to Make Mountain Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Minimum Number of Removals to Make Mountain Array is a hard coding problem on arrays, dynamic programming and greedy, asked in Amazon, Google and Microsoft interviews.

Problem statement

An array arr is a mountain when arr.length >= 3 and there is a peak index i with 0 < i < arr.length - 1 such that the values strictly increase up to the peak and strictly decrease after it:

  • arr[0] < arr[1] < ... < arr[i]
  • arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Given an array nums, return the fewest elements you must delete (keeping the others in order) so that what remains is a mountain. The input is guaranteed to allow a mountain.

Example 1

Input: nums = [1,3,1]
Output: 0
Explanation: It is already a mountain.

Example 2

Input: nums = [2,1,1,5,6,2,3,1]
Output: 3
Explanation: Delete indices 0, 1 and 5 to keep [1,5,6,3,1].

Example 3

Input: nums = [4,3,2,1,1,2,3,1]
Output: 4
Explanation: Keep [1,2,3,1]; no five elements form a mountain.

Constraints

  • 3 <= nums.length <= 1000
  • 1 <= nums[i] <= 10^9
  • a mountain can always be made from nums

Hints for Minimum Number of Removals to Make Mountain Array

  1. Hint 1

    Fix the peak. The best mountain with that peak keeps the longest strictly increasing run of chosen values ending at it, and the longest strictly decreasing one starting from it.

  2. Hint 2

    Compute, for every index, the longest strictly increasing subsequence ending there (left to right) and the longest strictly decreasing subsequence starting there (right to left).

  3. Hint 3

    A peak is only valid if both sides have length at least 2 — otherwise one slope is empty. The answer is n - max(inc[i] + dec[i] - 1) over valid peaks.

How to solve Minimum Number of Removals to Make Mountain Array

Deleting the fewest elements means keeping the longest mountain subsequence. For a fixed peak, its two slopes are independent: a longest increasing subsequence ending at the peak and a longest decreasing subsequence starting at it.

Approach

  1. inc[i] = length of the longest strictly increasing subsequence ending at i: 1 + max(inc[j]) over j < i with nums[j] < nums[i].
  2. dec[i] = length of the longest strictly decreasing subsequence starting at i, computed the same way from the right.
  3. For each i with inc[i] >= 2 and dec[i] >= 2, the mountain peaking at i keeps inc[i] + dec[i] - 1 elements (the peak is counted twice).
  4. Return n minus the largest such kept length.

Why it works

The left slope uses only indices before the peak with values below it, the right slope only indices after it with values below it, so the two choices never interact and each can be maximised on its own. Every mountain has some peak, so taking the best peak covers all mountains.

Complexity

  • Time — O(n^2) (O(n log n) with patience sorting for the two LIS passes)
  • Space — O(n)

Pitfalls

  • A peak at the very start or end of the kept sequence is not a mountain: require inc[i] > 1 and dec[i] > 1.
  • Both slopes are strict — equal neighbours break a mountain, so compare with <, not <=.

Reference solution

Python

from typing import List

def minimumMountainRemovals(nums: List[int]) -> int:
    n = len(nums)
    inc = [1] * n
    dec = [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i] and inc[j] + 1 > inc[i]:
                inc[i] = inc[j] + 1
    for i in range(n - 1, -1, -1):
        for j in range(i + 1, n):
            if nums[j] < nums[i] and dec[j] + 1 > dec[i]:
                dec[i] = dec[j] + 1
    keep = 0
    for i in range(n):
        if inc[i] > 1 and dec[i] > 1:
            keep = max(keep, inc[i] + dec[i] - 1)
    return n - keep

Java

public static int minimumMountainRemovals(int[] nums) {
    int n = nums.length;
    int[] inc = new int[n], dec = new int[n];
    for (int i = 0; i < n; i++) {
        inc[i] = 1;
        for (int j = 0; j < i; j++) if (nums[j] < nums[i]) inc[i] = Math.max(inc[i], inc[j] + 1);
    }
    for (int i = n - 1; i >= 0; i--) {
        dec[i] = 1;
        for (int j = i + 1; j < n; j++) if (nums[j] < nums[i]) dec[i] = Math.max(dec[i], dec[j] + 1);
    }
    int keep = 0;
    for (int i = 0; i < n; i++) if (inc[i] > 1 && dec[i] > 1) keep = Math.max(keep, inc[i] + dec[i] - 1);
    return n - keep;
}

C++

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

JavaScript

var minimumMountainRemovals = function(nums) {
    var n = nums.length, inc = new Array(n).fill(1), dec = new Array(n).fill(1);
    for (var i = 0; i < n; i++)
        for (var j = 0; j < i; j++)
            if (nums[j] < nums[i] && inc[j] + 1 > inc[i]) inc[i] = inc[j] + 1;
    for (var i = n - 1; i >= 0; i--)
        for (var j = i + 1; j < n; j++)
            if (nums[j] < nums[i] && dec[j] + 1 > dec[i]) dec[i] = dec[j] + 1;
    var keep = 0;
    for (var i = 0; i < n; i++)
        if (inc[i] > 1 && dec[i] > 1 && inc[i] + dec[i] - 1 > keep) keep = inc[i] + dec[i] - 1;
    return n - keep;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming