Minimum Number of Removals to Make Mountain Array
01 · Problem
Call an array a mountain when it has at least 3 elements and there is some peak index p with 0 < p < length - 1 such that the values strictly increase from index 0 up to p and then strictly decrease from p to the last index. Plateaus (equal neighbours) are not allowed on either side.
You are given an integer array nums. You may delete any elements you like; the remaining elements keep their original relative order. Return the smallest number of deletions needed so that what remains is a mountain.
The input is guaranteed to allow at least one mountain to be formed.
02 · Examples
nums = [1,3,1]
0
The array already climbs strictly to 3 and then drops strictly, so nothing needs to be removed.
nums = [4,2,5,7,3,1]
1
Removing the 4 leaves [2,5,7,3,1], which rises strictly to 7 and then falls strictly. One removal is the minimum because the original array dips from 4 to 2 before the peak.
nums = [2,1,1,5,6,2,3,1]
3
One optimal choice removes the values at indices 0, 1 and 5, leaving [1,5,6,3,1].
03 · Constraints
- 013 <= nums.length <= 1000
- 021 <= nums[i] <= 109
- 03It is guaranteed that some sequence of deletions turns nums into a mountain array
04 · Optimal complexity
- Time
- O(n log n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.