Watch 10 video solutions for Minimum Number of Removals to Make Mountain Array, a hard level problem involving Array, Binary Search, Dynamic Programming. This walkthrough by NeetCodeIO has 11,455 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You may recall that an array arr is a mountain array if and only if:
arr.length >= 3i (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 <= 10001 <= nums[i] <= 109nums.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 | 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 |