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.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Greedy, Binary Search
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 10001 <= nums[i] <= 10^9a mountain can always be made from nums
Hints for Minimum Number of Removals to Make Mountain Array
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.
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).
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
inc[i]= length of the longest strictly increasing subsequence ending ati:1 + max(inc[j])overj < iwithnums[j] < nums[i].dec[i]= length of the longest strictly decreasing subsequence starting ati, computed the same way from the right.- For each
iwithinc[i] >= 2anddec[i] >= 2, the mountain peaking atikeepsinc[i] + dec[i] - 1elements (the peak is counted twice). - Return
nminus 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] > 1anddec[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 - keepJava
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