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.
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.
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.
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.
Time Complexity: O(n^2), requiring traversal through sequences twice with nested loops.
Space Complexity: O(n) due to additional arrays retaining incremental results.
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.
| Approach | Complexity |
|---|---|
| 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. |
| Greedy Two-Pointer Technique | Time Complexity: O(n^2), requiring traversal through sequences twice with nested loops. |
| Dynamic Programming | — |
| 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 |
Minimum Number of Removals to Make Mountain Array - Leetcode 1671 - Python • NeetCodeIO • 11,455 views views
Watch 9 more video solutions →Practice Minimum Number of Removals to Make Mountain Array with our built-in code editor and test cases.
Practice on FleetCode