HardNo. 1671
Minimum Number of Removals to Make Mountain Array — LeetCode 1671 Python Solution
- Pattern
- Monotonic Stack
- Topics
- Greedy, Array, Binary Search, Dynamic Programming
- Reading time
- 3 min
- Source
- leetcode.com
The problem
You may recall that an array arr is a mountain array if and only if: arr.length >= 3 There exists some index i (0-indexed) with 0 < i < arr.length - 1 such that: arr[0] < arr[1] < ... < arr[i - 1] < arr[i] arr[i] > arr[i + 1] > ...
Example
- Input
- nums = [1,3,1]
- Output
- 0
- Explanation
- The array itself is a mountain array so we do not need to remove any elements.
Python solution
class Solution:
def minimumMountainRemovals(self, nums: List[int]) -> int:
n = len(nums)
left = [1] * n
right = [1] * n
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
left[i] = max(left[i], left[j] + 1)
for i in range(n - 2, -1, -1):
for j in range(i + 1, n):
if nums[i] > nums[j]:
right[i] = max(right[i], right[j] + 1)
return n - max(a + b - 1 for a, b in zip(left, right) if a > 1 and b > 1)Complexity
- Time
- O(n2)
- Space · auxiliary
- O(n)
Pattern: Monotonic Stack
Answer "what is the next greater element" for every position in one pass. LeetCode 1671. Minimum Number of Removals to Make Mountain Array is filed here because the reference solution below belongs to the algorithm family this hub collects, even though its LeetCode tags point elsewhere.
The monotonic stack guide has the Python template for the pattern and the 225 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0410 | Split Array Largest Sum | Hard |
| 2439 | Minimize Maximum of Array | Medium |
| 2560 | House Robber IV | Medium |
| 2616 | Minimize the Maximum Difference of Pairs | Medium |
| 0300 | Longest Increasing Subsequence | Medium |
| 0354 | Russian Doll Envelopes | Hard |
Frequently asked questions
- How hard is LeetCode 1671. Minimum Number of Removals to Make Mountain Array?
LeetCode 1671. Minimum Number of Removals to Make Mountain Array is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1671. Minimum Number of Removals to Make Mountain Array?
The Python solution on this page runs in O(n2).
- What is the space complexity of LeetCode 1671. Minimum Number of Removals to Make Mountain Array?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1671. Minimum Number of Removals to Make Mountain Array cover?
LeetCode 1671. Minimum Number of Removals to Make Mountain Array is tagged Greedy, Array, Binary Search and Dynamic Programming on LeetCode.