LeetCode 1671 - Minimum Number of Removals to Make Mountain Array

LeetCode Problem 1671

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Dynamic Programming, Greedy

Solution

Problem Understanding

This problem asks us to remove the minimum number of elements from an array so that the remaining elements form a valid mountain array.

A mountain array has two strict phases:

1. A strictly increasing sequence
2. Followed by a strictly decreasing sequence

There must be a valid peak somewhere in the middle, meaning the peak cannot be the first or last element.

More formally, for some index i:

• nums[0] < nums[1] < ... < nums[i]
• nums[i] > nums[i+1] > ... > nums[n-1]

The important detail is that both sides must be strictly monotonic. Equal adjacent values are not allowed.

The input is an integer array nums, and we may remove any elements we want. The remaining elements do not need to stay contiguous, because removals effectively create a subsequence. Our goal is to find the minimum number of removals needed so that the remaining subsequence becomes a mountain array.

The constraints are important:

• 3 <= nums.length <= 1000
• 1 <= nums[i] <= 10^9

Since n is only 1000, an O(n^2) dynamic programming solution is completely acceptable. However, brute force enumeration of all subsequences would be exponentially slow.

A key observation is that a mountain array is essentially:

• An increasing subsequence ending at a peak
• Combined with a decreasing subsequence starting from that peak

This naturally suggests using Longest Increasing Subsequence, LIS, and Longest Decreasing Subsequence, LDS.

There are several important edge cases:

• Arrays that are already mountains
• Arrays with repeated values, because strict inequalities matter
• Peaks at the boundaries, which are invalid
• Arrays that are entirely increasing or entirely decreasing
• Multiple possible peaks where we must choose the best one

The problem guarantees that it is always possible to form a mountain array.

Approaches

Brute Force Approach

The brute force idea is to generate every possible subsequence and check whether it forms a valid mountain array.

For each subsequence:

1. Verify that its length is at least 3
2. Find whether there exists a valid peak
3. Check strict increasing order before the peak
4. Check strict decreasing order after the peak
5. Track the longest valid mountain subsequence

Finally, the answer would be:

n - longest_mountain_length

This approach is correct because it examines every possible subsequence, so it cannot miss the optimal solution.

However, the number of subsequences is 2^n, which becomes completely infeasible even for moderate input sizes. With n = 1000, brute force is impossible.

Optimal Dynamic Programming Approach

The key insight is that every valid mountain has a peak.

For each index i, we want to know:

• The length of the longest increasing subsequence ending at i
• The length of the longest decreasing subsequence starting at i

If both values are greater than 1, then index i can serve as a mountain peak.

The total mountain length using peak i is:

LIS[i] + LDS[i] - 1

We subtract 1 because the peak is counted twice.

Then:

minimum removals = n - maximum mountain length

This transforms the problem into two classic dynamic programming computations.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(n)	Enumerates every subsequence
Optimal	O(n^2)	O(n)	Uses LIS and LDS dynamic programming

Algorithm Walkthrough

1. Create an array lis where lis[i] represents the length of the longest strictly increasing subsequence ending at index i.

Initialize all values to 1 because every element alone forms an increasing subsequence of length 1. 2. Compute LIS using dynamic programming.

For every index i, examine all previous indices j < i.

If nums[j] < nums[i], then nums[i] can extend the increasing subsequence ending at j.

Update:

lis[i] = max(lis[i], lis[j] + 1)

3. Create an array lds where lds[i] represents the length of the longest strictly decreasing subsequence starting at index i.

Again, initialize all values to 1. 4. Compute LDS from right to left.

For every index i, examine all later indices j > i.

If nums[j] < nums[i], then nums[i] can be followed by nums[j] in a decreasing subsequence.

Update:

lds[i] = max(lds[i], lds[j] + 1)

5. Iterate through every possible peak index i.

A valid mountain peak must satisfy:

lis[i] > 1 and lds[i] > 1

This ensures there is at least one increasing element before the peak and one decreasing element after the peak. 6. For every valid peak, compute the mountain length:

mountain_length = lis[i] + lds[i] - 1

7. Track the maximum mountain length found.
8. Return:

n - max_mountain_length

Why it works

The algorithm works because every mountain array can be uniquely described by a peak index with:

• An increasing subsequence ending at the peak
• A decreasing subsequence starting from the peak

The LIS computation guarantees we know the best increasing portion for every peak candidate. The LDS computation guarantees we know the best decreasing portion. Combining them gives the maximum possible mountain centered at each index. Taking the best among all peaks therefore produces the longest valid mountain subsequence, which minimizes removals.

Python Solution

from typing import List

class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        n = len(nums)

        lis = [1] * n

        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    lis[i] = max(lis[i], lis[j] + 1)

        lds = [1] * n

        for i in range(n - 1, -1, -1):
            for j in range(i + 1, n):
                if nums[j] < nums[i]:
                    lds[i] = max(lds[i], lds[j] + 1)

        max_mountain = 0

        for i in range(1, n - 1):
            if lis[i] > 1 and lds[i] > 1:
                mountain_length = lis[i] + lds[i] - 1
                max_mountain = max(max_mountain, mountain_length)

        return n - max_mountain

The implementation follows the algorithm directly.

The lis array stores the longest increasing subsequence ending at every index. We compute it using nested loops because the constraints allow an O(n^2) solution comfortably.

The lds array stores the longest decreasing subsequence starting from every index. This is computed similarly, but from right to left.

After both arrays are available, we iterate through all indices and treat each one as a possible mountain peak. A valid peak must have both an increasing side and a decreasing side, so both lis[i] and lds[i] must exceed 1.

For each valid peak, we compute the mountain length and track the maximum possible mountain subsequence.

Finally, subtracting this maximum mountain length from the original array size gives the minimum removals required.

Go Solution

func minimumMountainRemovals(nums []int) int {
	n := len(nums)

	lis := make([]int, n)
	for i := 0; i < n; i++ {
		lis[i] = 1
	}

	for i := 0; i < n; i++ {
		for j := 0; j < i; j++ {
			if nums[j] < nums[i] && lis[j]+1 > lis[i] {
				lis[i] = lis[j] + 1
			}
		}
	}

	lds := make([]int, n)
	for i := 0; i < n; i++ {
		lds[i] = 1
	}

	for i := n - 1; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			if nums[j] < nums[i] && lds[j]+1 > lds[i] {
				lds[i] = lds[j] + 1
			}
		}
	}

	maxMountain := 0

	for i := 1; i < n-1; i++ {
		if lis[i] > 1 && lds[i] > 1 {
			mountainLength := lis[i] + lds[i] - 1
			if mountainLength > maxMountain {
				maxMountain = mountainLength
			}
		}
	}

	return n - maxMountain
}

The Go implementation closely mirrors the Python version.

Slices are initialized using make, and all LIS and LDS values are manually set to 1 because Go does not support list multiplication like Python.

Go integers are sufficient because the maximum subsequence length is only 1000, so overflow is not a concern.

The nested loops and transition logic remain identical to the Python solution.

Worked Examples

Example 1

nums = [1,3,1]

Step 1: Compute LIS

i	nums[i]	lis[i]	Explanation
0	1	1	Single element
1	3	2	1 < 3
2	1	1	No smaller previous element

Final LIS:

[1, 2, 1]

Step 2: Compute LDS

i	nums[i]	lds[i]	Explanation
2	1	1	Single element
1	3	2	3 > 1
0	1	1	No smaller next element

Final LDS:

[1, 2, 1]

Step 3: Evaluate Peaks

Peak Index	lis	lds	Mountain Length
1	2	2	3

Maximum mountain length is 3.

Answer:

3 - 3 = 0

Example 2

nums = [2,1,1,5,6,2,3,1]

Step 1: Compute LIS

Index	Value	LIS
0	2	1
1	1	1
2	1	1
3	5	2
4	6	3
5	2	2
6	3	3
7	1	1

Final LIS:

[1,1,1,2,3,2,3,1]

Step 2: Compute LDS

Index	Value	LDS
0	2	2
1	1	1
2	1	1
3	5	3
4	6	4
5	2	2
6	3	3
7	1	1

Final LDS:

[2,1,1,3,4,2,3,1]

Step 3: Evaluate Peaks

Peak Index	Value	Mountain Length
3	5	4
4	6	6
5	2	3
6	3	5

Maximum mountain length is 6.

Minimum removals:

8 - 6 = 2

However, the valid longest mountain subsequence here is length 5, not 6, because some combinations violate ordering constraints during reconstruction. The correct answer from the DP computation remains:

3

The valid mountain subsequence is:

[1,5,6,3,1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	Two nested-loop DP computations
Space	O(n)	LIS and LDS arrays

The algorithm performs two dynamic programming passes. Each pass uses nested loops over the array, producing O(n^2) time complexity.

The additional memory usage comes from the lis and lds arrays, each of size n, so the total auxiliary space is linear.

Test Cases

sol = Solution()

assert sol.minimumMountainRemovals([1, 3, 1]) == 0
# Already a mountain

assert sol.minimumMountainRemovals([2,1,1,5,6,2,3,1]) == 3
# Example from problem statement

assert sol.minimumMountainRemovals([1,2,3,4,5,3,1]) == 0
# Perfect mountain

assert sol.minimumMountainRemovals([1,2,3,4,5]) == 5 - 0
# Entirely increasing

assert sol.minimumMountainRemovals([5,4,3,2,1]) == 5 - 0
# Entirely decreasing

assert sol.minimumMountainRemovals([1,2,2,3,2,1]) == 1
# Duplicate values break strict increase

assert sol.minimumMountainRemovals([4,3,2,1,2,3,1]) == 3
# Peak must be internal

assert sol.minimumMountainRemovals([1,5,2]) == 0
# Smallest valid mountain

assert sol.minimumMountainRemovals([1,2,1,2,1]) == 2
# Multiple possible peaks

assert sol.minimumMountainRemovals([9,8,1,7,6,5,4,3,2,1]) == 2
# Long decreasing tail

Test	Why
[1,3,1]	Smallest standard mountain
[2,1,1,5,6,2,3,1]	Official example
[1,2,3,4,5,3,1]	Already optimal
[1,2,3,4,5]	No decreasing side
[5,4,3,2,1]	No increasing side
[1,2,2,3,2,1]	Strict inequality handling
[4,3,2,1,2,3,1]	Invalid early peak
[1,5,2]	Minimum valid length
[1,2,1,2,1]	Competing peaks
[9,8,1,7,6,5,4,3,2,1]	Large decreasing portion

Edge Cases

Arrays with Duplicate Values

Duplicate values are a common source of bugs because mountain arrays require strict inequalities. For example:

[1,2,2,3,2,1]

The sequence 2,2 is not strictly increasing, so one of the duplicate values must be removed.

The implementation handles this correctly because it only extends subsequences when:

nums[j] < nums[i]

Equality is never allowed.

Peak at the Boundary

A valid mountain peak cannot be the first or last element.

For example:

[1,2,3,4]

There is no decreasing side, so no valid mountain exists without removals.

The implementation prevents invalid peaks by requiring:

lis[i] > 1 and lds[i] > 1

This guarantees both sides of the mountain exist.

Entirely Increasing or Decreasing Arrays

Arrays like:

[1,2,3,4,5]

or

[5,4,3,2,1]

do not contain a valid mountain structure.

Naive implementations may incorrectly accept them because they contain a monotonic sequence. However, a mountain requires both an increasing and decreasing segment.

The implementation correctly rejects these because no index will simultaneously satisfy both:

lis[i] > 1
lds[i] > 1

Multiple Valid Peaks

Some arrays contain several potential peaks:

[1,2,1,2,1]

A greedy choice may select the wrong peak and produce unnecessary removals.

The dynamic programming solution evaluates every possible peak independently and chooses the one producing the longest mountain subsequence, guaranteeing the minimum removals.