816. Fewest Removals for a Mountain
A trail-builder lists elevations along a path in nums and may delete some of them. The remaining elevations, in their original order, must form a mountain: at least three values, strictly increasing up to a single peak and then strictly decreasing, with the peak neither first nor last.
Return the minimum number of elevations that must be deleted to get a mountain. If no mountain can be formed whatever you delete (for example when the list is too short or never rises and falls), return -1.
Aim for time O(n log n) and extra space O(n), where n is the length of nums.
Example 1
- Input:
- nums = [2,6,9,4,3,7,1]
- Output:
- 1
- Explanation:
Removing only the 7 leaves 2, 6, 9, 4, 3, 1: it rises to 9 then falls, so one removal is enough.
Example 2
- Input:
- nums = [3,8,8,5,6,2]
- Output:
- 2
- Explanation:
Removing the second 8 and the 6 leaves 3, 8, 5, 2, a mountain after 2 removals.
Constraints
1 ≤ nums.length ≤ 100000
1 ≤ nums[i] ≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)