NeetCode #702LC-1671Hard1-D Dynamic Programming
← Back to All Problems#702 · #1671 · Minimum Number of Removals to Make Mountain Array(得到山形数组的最少删除次数)
📌 Problem Statement & Constraints
Given
nums, return the minimum number of elements to remove so that the remaining array is a mountain array: strictly increasing up to a peak index and strictly decreasing afterwards, with at least three elements. Constraints: 1 <= nums.length <= 1000, 1 <= nums[i] <= 10^9.💡 Core Algorithmic Approaches
- Compute
inc[i], the length of the longest strictly increasing subsequence ending ati. - Compute
dec[i], the length of the longest strictly decreasing subsequence starting ati. - For every valid peak (
inc[i] >= 2anddec[i] >= 2), the largest mountain isinc[i] + dec[i] - 1. - The answer is
nminus the largest such mountain; the peak needs a strictly smaller neighbour on both sides, hence the>= 2guards.
💻 Benchmark Python3 Implementation
class Solution:
def minimumMountainRemovals(self, nums: List[int]) -> int:
n = len(nums)
inc = [1] * n
for i in range(n):
for j in range(i):
if nums[j] < nums[i]:
inc[i] = max(inc[i], inc[j] + 1)
dec = [1] * n
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
if nums[j] < nums[i]:
dec[i] = max(dec[i], dec[j] + 1)
best = 0
for i in range(n):
if inc[i] >= 2 and dec[i] >= 2: # a peak needs both sides
best = max(best, inc[i] + dec[i] - 1)
return n - best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n^2): the two LIS passes; an O(n log n) variant uses patience sorting.
💾 Space Complexity
O(n): the inc and dec arrays.
⚠️ Interview Pitfalls & Follow-ups
- Dropping the
inc[i] >= 2 and dec[i] >= 2guard: an index with only one side is not a valid peak, so the mountain length would be understated. - Using non-strict comparisons: the mountain is strictly increasing then strictly decreasing, so
nums[j] < nums[i]is required. - Computing
decleft to right: it is the longest decreasing subsequence starting ati, so the loop runs right to left. - Returning the mountain length: the problem asks for removals, which is
n - best.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.