⚡Flashcard Drill➔
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

  1. Compute inc[i], the length of the longest strictly increasing subsequence ending at i.
  2. Compute dec[i], the length of the longest strictly decreasing subsequence starting at i.
  3. For every valid peak (inc[i] >= 2 and dec[i] >= 2), the largest mountain is inc[i] + dec[i] - 1.
  4. The answer is n minus the largest such mountain; the peak needs a strictly smaller neighbour on both sides, hence the >= 2 guards.

💻 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] >= 2 guard: 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 dec left to right: it is the longest decreasing subsequence starting at i, 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.
🎯 Drill This Card Now➔

🧩 Related 1-D Dynamic Programming Problems