Skip to main content
Talentd

Minimum Number of Removals to Make Mountain Array - Solution & Explanation

HardArrayBinary SearchDynamic ProgrammingGreedy20 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

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] <= 109
  • 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.

This C solution calculates the LIS and LDS for each index in the array using dynamic programming. It then scans for indices that can serve as peaks in a mountain array, where both LIS and LDS are greater than 1. The length of such a mountain is computed, and the minimum removals are the array's total length minus this length.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), where n is the length of the array, due to the nested loops to calculate LIS and LDS.
Space Complexity: O(n) for the LIS and LDS arrays.

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.

This C solution uses two separate passes to identify the longest increasing and decreasing sequences through the list. By leveraging two pointer variables across arrays (capturing differences in sequences), effective merging occurs. Reduction of the sequence only removes minimal elements required.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^2), requiring traversal through sequences twice with nested loops.
Space Complexity: O(n) due to additional arrays retaining incremental results.

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.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Dynamic Programming with Longest Increasing and Decreasing Subsequences

Time Complexity: O(n^2), where n is the length of the array, due to the nested loops to calculate LIS and LDS.
Space Complexity: O(n) for the LIS and LDS arrays.

Greedy Two-Pointer Technique

Time Complexity: O(n^2), requiring traversal through sequences twice with nested loops.
Space Complexity: O(n) due to additional arrays retaining incremental results.

Dynamic Programming—

Detailed Complexity Analysis

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

Video Solution

Minimum Number of Removals to Make Mountain Array - Leetcode 1671 - Python • NeetCodeIO • 11,722 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Minimum Number of Removals to Make Mountain Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Beautiful Towers I

Next

Beautiful Towers II