1671. Minimum Removals to Make Mountain Array - Solution

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] > ... > arr[arr.length - 1]

Given an integer array nums, return the minimum number of elements to remove to make nums a mountain array.

Example 1:

Input: nums = [1,3,1]
Output: 0
Explanation: The array itself is a mountain array so we do not need to remove any elements.

Example 2:

Input: nums = [2,1,1,5,6,2,3,1]
Output: 3
Explanation: One solution is to remove the elements at indices 0, 1, and 5, making the array nums = [1,5,6,3,1].

Constraints:

3 <= nums.length <= 1000
1 <= nums[i] <= 10⁹
It is guaranteed that you can make a mountain array out of nums.

Approach overview

Problem Overview: Given an integer array, remove the minimum number of elements so the remaining sequence forms a mountain array. A valid mountain strictly increases to a peak and then strictly decreases, and the peak cannot be the first or last element.

Approach 1: Dynamic Programming with LIS and LDS (O(n log n) time, O(n) space)

The key observation: a valid mountain has an increasing part ending at index i and a decreasing part starting at i. Compute the Longest Increasing Subsequence (LIS) length ending at every index using binary search optimization. Then compute the Longest Decreasing Subsequence (LDS) starting from every index by processing the array in reverse. For each index i, if lis[i] > 1 and lds[i] > 1, it can serve as the peak of a mountain. The mountain length becomes lis[i] + lds[i] - 1. Track the maximum possible mountain and subtract it from n to get the minimum removals. The binary-search LIS optimization keeps the solution at O(n log n). This approach heavily relies on dynamic programming and binary search over an array.

Approach 2: Greedy Two-Pointer Technique (O(n^2) time, O(n) space)

Another perspective is to treat each index as a potential peak and expand outward while maintaining strictly increasing and decreasing sequences. For a chosen peak, move a pointer left while ensuring values strictly increase toward the peak, and move a pointer right while values strictly decrease away from the peak. This effectively simulates building a mountain around each candidate peak. Track the longest valid mountain found and compute removals as n - mountainLength. The method is straightforward and uses a greedy local decision process, but evaluating every possible peak leads to O(n^2) time in the worst case.

Recommended for interviews: The LIS + LDS dynamic programming solution is the expected answer. It demonstrates understanding of subsequence DP and how to combine two directional passes to model a peak structure. Starting with a brute-force or greedy idea shows reasoning, but optimizing it to the O(n log n) LIS-based approach signals strong algorithmic skill.

Approach 1: Dynamic Programming with Longest Increasing and Decreasing Subsequences

This approach involves finding the longest increasing subsequence (LIS) ending at each index and the longest decreasing subsequence (LDS) starting from each index. The idea is to find a peak such that the sum of the longest increasing and decreasing subsequences is maximized, and then determine how many elements need to be removed such that only the peak and the subsequences are left.

Python

def minMountainRemovals(nums):
    n = len(nums)
    lis = [1] * n
    lds = [1] * n

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

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

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

    return n - max_mountain

Java

public class Solution {
    public int minMountainRemovals(int[] nums) {
        int n = nums.length;
        int[] lis = new int[n];
        int[] lds = new int[n];
        Arrays.fill(lis, 1);
        Arrays.fill(lds, 1);

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    lis[i] = Math.max(lis[i], lis[j] + 1);
                }
            }
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j > i; j--) {
                if (nums[i] > nums[j]) {
                    lds[i] = Math.max(lds[i], lds[j] + 1);
                }
            }
        }

        int maxMountain = 0;
        for (int i = 0; i < n; i++) {
            if (lis[i] > 1 && lds[i] > 1) {
                maxMountain = Math.max(maxMountain, lis[i] + lds[i] - 1);
            }
        }

        return n - maxMountain;
    }
}

C++

#include <vector>
using namespace std;

int minMountainRemovals(vector<int>& nums) {
    int n = nums.size();
    vector<int> lis(n, 1), lds(n, 1);

    // Compute LIS for each index
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < i; ++j)
            if (nums[i] > nums[j])
                lis[i] = max(lis[i], lis[j] + 1);

    // Compute LDS for each index
    for (int i = n - 1; i >= 0; --i)
        for (int j = n - 1; j > i; --j)
            if (nums[i] > nums[j])
                lds[i] = max(lds[i], lds[j] + 1);

    int maxMountain = 0;
    for (int i = 0; i < n; ++i)
        if (lis[i] > 1 && lds[i] > 1)
            maxMountain = max(maxMountain, lis[i] + lds[i] - 1);

    return n - maxMountain;
}

JavaScript

function minMountainRemovals(nums) {
    const n = nums.length;
    const lis = Array(n).fill(1);
    const lds = Array(n).fill(1);

    for (let i = 0; i < n; i++)
        for (let j = 0; j < i; j++)
            if (nums[i] > nums[j]) lis[i] = Math.max(lis[i], lis[j] + 1);

    for (let i = n - 1; i >= 0; i--)
        for (let j = n - 1; j > i; j--)
            if (nums[i] > nums[j]) lds[i] = Math.max(lds[i], lds[j] + 1);

    let maxMountain = 0;
    for (let i = 0; i < n; i++)
        if (lis[i] > 1 && lds[i] > 1)
            maxMountain = Math.max(maxMountain, lis[i] + lds[i] - 1);

    return n - maxMountain;
}

#include <stdio.h>
#include <string.h>

#define MAX(x, y) ((x) > (y) ? (x) : (y))

int minMountainRemovals(int* nums, int numsSize) {
    int lis[numsSize], lds[numsSize];
    int i, j;
    memset(lis, 0, sizeof(lis));
    memset(lds, 0, sizeof(lds));

    // Calculate LIS for every index
    for (i = 0; i < numsSize; i++) {
        lis[i] = 1;
        for (j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                lis[i] = MAX(lis[i], lis[j] + 1);
            }
        }
    }

    // Calculate LDS for every index
    for (i = numsSize - 1; i >= 0; i--) {
        lds[i] = 1;
        for (j = numsSize - 1; j > i; j--) {
            if (nums[i] > nums[j]) {
                lds[i] = MAX(lds[i], lds[j] + 1);
            }
        }
    }

    int maxMountain = 0;
    for (i = 0; i < numsSize; i++) {
        if (lis[i] > 1 && lds[i] > 1) {
            maxMountain = MAX(maxMountain, lis[i] + lds[i] - 1);
        }
    }

    return numsSize - maxMountain;
}

public class Solution {
    public int MinMountainRemovals(int[] nums) {
        int n = nums.Length;
        int[] lis = new int[n];
        int[] lds = new int[n];

        for (int i = 0; i < n; i++) {
            lis[i] = 1;
            for (int j = 0; j < i; j++)
                if (nums[i] > nums[j]) lis[i] = Math.Max(lis[i], lis[j] + 1);
        }

        for (int i = n - 1; i >= 0; i--) {
            lds[i] = 1;
            for (int j = n - 1; j > i; j--)
                if (nums[i] > nums[j]) lds[i] = Math.Max(lds[i], lds[j] + 1);
        }

        int maxMountain = 0;
        for (int i = 0; i < n; i++) {
            if (lis[i] > 1 && lds[i] > 1)
                maxMountain = Math.Max(maxMountain, lis[i] + lds[i] - 1);
        }
        return n - maxMountain;
    }
}

This Python solution calculates LIS and LDS for the array using nested loops. Then, it checks for valid peaks where both LIS and LDS are more than one. It returns minimum removals by subtracting the maximum mountain length from the total number of elements.

Complexity

Time Complexity: O(n^2), as operations for LIS and LDS involve iterating over the pairs of elements.
Space Complexity: O(n), for auxiliary arrays storing LIS and LDS values.

Try this approach in the editor

Approach 2: Greedy Two-Pointer Technique

This method involves a greedy approach using two-pointer strategy to find potential mountain peaks. We employ two pointers to detect increasing and decreasing sequences, merging the results to form the largest mountain, iteratively removing non-peak elements.

Python

def minMountainRemovals(nums):
    n = len(nums)
    lis = [1] * n
    lds = [1] * n

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

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

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

    return n - max_mountain

Java

import java.util.Arrays; 
class Solution {
    public int minMountainRemovals(int[] nums) {
        int n = nums.length; 
        int[] lis = new int[n]; 
        int[] lds = new int[n]; 
        Arrays.fill(lis, 1); 
        Arrays.fill(lds, 1); 

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    lis[i] = Math.max(lis[i], lis[j] + 1); 
                }
            }
        }

        for (int i = n - 1; i >= 0; i--) {
            for (int j = n - 1; j > i; j--) {
                if (nums[i] > nums[j]) {
                    lds[i] = Math.max(lds[i], lds[j] + 1);
                }
            }
        }

        int maxMountain = 0; 
        for (int i = 0; i < n; i++) {
            if (lis[i] > 1 && lds[i] > 1) {
                maxMountain = Math.max(maxMountain, lis[i] + lds[i] - 1); 
            }
        }

        return n - maxMountain; 
    }
}

C++

#include <vector>
#include <algorithm>
using namespace std;

int minMountainRemovals(vector<int>& nums) {
    int n = nums.size();
    vector<int> lis(n, 1), lds(n, 1);
    
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < i; ++j)
            if (nums[i] > nums[j]) lis[i] = max(lis[i], lis[j] + 1);

    for (int i = n - 1; i >= 0; --i)
        for (int j = n - 1; j > i; --j)
            if (nums[i] > nums[j]) lds[i] = max(lds[i], lds[j] + 1);

    int maxMountain = 0;
    for (int i = 0; i < n; ++i)
        if (lis[i] > 1 && lds[i] > 1)
            maxMountain = max(maxMountain, lis[i] + lds[i] - 1);

    return n - maxMountain;
}

JavaScript

function minMountainRemovals(nums) {
    const n = nums.length;
    const lis = new Array(n).fill(1);
    const lds = new Array(n).fill(1);

    for (let i = 0; i < n; ++i) {
        for (let j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) lis[i] = Math.max(lis[i], lis[j] + 1);
        }
    }

    for (let i = n - 1; i >= 0; --i) {
        for (let j = n - 1; j > i; --j) {
            if (nums[i] > nums[j]) lds[i] = Math.max(lds[i], lds[j] + 1);
        }
    }

    let maxMountain = 0;
    for (let i = 0; i < n; ++i) {
        if (lis[i] > 1 && lds[i] > 1) {
            maxMountain = Math.max(maxMountain, lis[i] + lds[i] - 1);
        }
    }

    return n - maxMountain;
}

#include <stdio.h>
#include <string.h>

int minMountainRemovals(int* nums, int numsSize) {
    // Finding the longest increasing sequence
    int dp_inc[numsSize];
    memset(dp_inc, 0, sizeof(dp_inc));
    for (int i = 0; i < numsSize; ++i) {
        dp_inc[i] = 1;
        for (int j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                dp_inc[i] = (dp_inc[i] > (dp_inc[j] + 1)) ? dp_inc[i] : (dp_inc[j] + 1);
            }
        }
    }

    // Finding the longest decreasing sequence
    int dp_dec[numsSize];
    memset(dp_dec, 0, sizeof(dp_dec));
    for (int i = numsSize - 1; i >= 0; --i) {
        dp_dec[i] = 1;
        for (int j = numsSize - 1; j > i; --j) {
            if (nums[i] > nums[j]) {
                dp_dec[i] = (dp_dec[i] > (dp_dec[j] + 1)) ? dp_dec[i] : (dp_dec[j] + 1);
            }
        }
    }

    // Calculate the max mountain size using the two arrays
    int max_size = 0;
    for (int i = 0; i < numsSize; ++i) {
        if (dp_inc[i] > 1 && dp_dec[i] > 1) { // Ensure peak is valid
            max_size = (max_size > (dp_inc[i] + dp_dec[i] - 1)) ? max_size : (dp_inc[i] + dp_dec[i] - 1);
        }
    }

    return numsSize - max_size;
}

public class Solution {
    public int MinMountainRemovals(int[] nums) {
        int n = nums.Length; 
        int[] lis = new int[n]; 
        int[] lds = new int[n]; 

        for (int i = 0; i < n; i++) {
            lis[i] = 1; 
            for (int j = 0; j < i; j++)
                if (nums[i] > nums[j]) 
                    lis[i] = Math.Max(lis[i], lis[j] + 1); 
        } 

        for (int i = n - 1; i >= 0; i--) {
            lds[i] = 1; 
            for (int j = n - 1; j > i; j--)
                if (nums[i] > nums[j])
                    lds[i] = Math.Max(lds[i], lds[j] + 1);
        }

        int maxMountain = 0; 
        for (int i = 0; i < n; i++) {
            if (lis[i] > 1 && lds[i] > 1)
                maxMountain = Math.Max(maxMountain, lis[i] + lds[i] - 1);
        }

        return n - maxMountain; 
    }
}

In Python, the two-pointer based approach translates into relatively straightforward list operations, along with sequence splitting. Ultimately, increased attention to sequence analysis ensures minimal removals while sustaining mountainous cohesion.

Complexity

Time Complexity: O(n^2), requiring nested looping for simultaneous iterations.
Space Complexity: O(n) owing to list resource allocation during sequential steps.

Try this approach in the editor

Approach 3: Dynamic Programming

This problem can be transformed into finding the longest increasing subsequence and the longest decreasing subsequence.

We define left[i] as the length of the longest increasing subsequence ending with nums[i], and define right[i] as the length of the longest decreasing subsequence starting with nums[i].

Then the final answer is n - max(left[i] + right[i] - 1), where 1 leq i leq n, and left[i] \gt 1 and right[i] \gt 1.

The time complexity is O(n^2), and the space complexity is O(n). Here, n is the length of the array nums.

TypeScript

function minimumMountainRemovals(nums: number[]): number {
    const n = nums.length;
    const left = Array(n).fill(1);
    const right = Array(n).fill(1);
    for (let i = 1; i < n; ++i) {
        for (let j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                left[i] = Math.max(left[i], left[j] + 1);
            }
        }
    }
    for (let i = n - 2; i >= 0; --i) {
        for (let j = i + 1; j < n; ++j) {
            if (nums[i] > nums[j]) {
                right[i] = Math.max(right[i], right[j] + 1);
            }
        }
    }
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        if (left[i] > 1 && right[i] > 1) {
            ans = Math.max(ans, left[i] + right[i] - 1);
        }
    }
    return n - ans;
}

func minimumMountainRemovals(nums []int) int {
	n := len(nums)
	left, right := make([]int, n), make([]int, n)
	for i := range left {
		left[i], right[i] = 1, 1
	}
	for i := 1; i < n; i++ {
		for j := 0; j < i; j++ {
			if nums[i] > nums[j] {
				left[i] = max(left[i], left[j]+1)
			}
		}
	}
	for i := n - 2; i >= 0; i-- {
		for j := i + 1; j < n; j++ {
			if nums[i] > nums[j] {
				right[i] = max(right[i], right[j]+1)
			}
		}
	}
	ans := 0
	for i := range left {
		if left[i] > 1 && right[i] > 1 {
			ans = max(ans, left[i]+right[i]-1)
		}
	}
	return n - ans
}

Rust

impl Solution {
    pub fn minimum_mountain_removals(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut left = vec![1; n];
        let mut right = vec![1; n];
        for i in 1..n {
            for j in 0..i {
                if nums[i] > nums[j] {
                    left[i] = left[i].max(left[j] + 1);
                }
            }
        }
        for i in (0..n - 1).rev() {
            for j in i + 1..n {
                if nums[i] > nums[j] {
                    right[i] = right[i].max(right[j] + 1);
                }
            }
        }

        let mut ans = 0;
        for i in 0..n {
            if left[i] > 1 && right[i] > 1 {
                ans = ans.max(left[i] + right[i] - 1);
            }
        }

        (n as i32) - ans
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Dynamic Programming with Longest Increasing and Decreasing Subsequences	Time Complexity: O(n^2), as operations for LIS and LDS involve iterating over the pairs of elements. Space Complexity: O(n), for auxiliary arrays storing LIS and LDS values.
Greedy Two-Pointer Technique	Time Complexity: O(n^2), requiring nested looping for simultaneous iterations. Space Complexity: O(n) owing to list resource allocation during sequential steps.
Dynamic Programming	–

Complexity analysis

Approach	Time	Space	When to Use
Dynamic Programming with LIS and LDS	O(n log n)	O(n)	General case and interview settings where optimal subsequence computation is required
Greedy Two-Pointer Peak Expansion	O(n^2)	O(n)	When explaining intuition or validating peak-based mountain construction

Frequently asked questions

Is Minimum Number of Removals to Make Mountain Array easy or hard?

The problem is rated Hard on LeetCode because it requires combining two subsequence dynamic programming passes and recognizing the peak constraint. Understanding LIS optimization with binary search is usually the main difficulty for candidates.

Minimum Number of Removals to Make Mountain Array Python/Java solution

Most implementations compute LIS and LDS arrays and then iterate through possible peaks. Python solutions typically use the bisect module for binary search, while Java solutions use Arrays.binarySearch or custom binary search logic. Both achieve O(n log n) time and O(n) space.

How to solve Minimum Number of Removals to Make Mountain Array in O(n log n)?

Compute the LIS length for every index using the patience sorting technique with binary search. Then compute the LDS by running the same process on the reversed array. For each index that has both lis[i] > 1 and lds[i] > 1, calculate the mountain length. The minimum removals equal n minus the maximum mountain length.

What is the best approach for Minimum Number of Removals to Make Mountain Array?

The best approach uses Longest Increasing Subsequence (LIS) and Longest Decreasing Subsequence (LDS). Compute LIS ending at each index and LDS starting at each index, then treat every index as a potential peak. The largest valid mountain length is lis[i] + lds[i] - 1. Subtract that from the array size to get the minimum removals. With binary search optimization, the time complexity is O(n log n).

Is Minimum Number of Removals to Make Mountain Array asked at Google/Amazon/Meta?

Mountain array and subsequence dynamic programming problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variations often test understanding of LIS, peak-based array transformations, and combining two dynamic programming passes across an array.

What data structure is used in Minimum Number of Removals to Make Mountain Array?

The solution primarily uses arrays to store LIS and LDS lengths for each index. Binary search is used with a dynamic list or vector to maintain the smallest possible tail values for subsequences, enabling O(log n) updates during LIS computation.

What is the time complexity of Minimum Number of Removals to Make Mountain Array?

The optimal solution runs in O(n log n) time by computing LIS and LDS using binary search. Each subsequence computation processes the array once while maintaining a sorted structure for efficient insertion. The space complexity is O(n) to store subsequence lengths for each index.

Minimum Number of Removals to Make Mountain Array solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Longest Increasing and Decreasing Subsequences

Approach 2: Greedy Two-Pointer Technique

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Minimum Number of Removals to Make Mountain Array solution and explanation

The problem

Approach overview

Approach 1: Dynamic Programming with Longest Increasing and Decreasing Subsequences

Approach 2: Greedy Two-Pointer Technique

Approach 3: Dynamic Programming

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems