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.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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2), requiring traversal through sequences twice with nested loops.
Space Complexity: O(n) due to additional arrays retaining incremental results.
| 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. |
Minimum Number of Removals to Make Mountain Array - Leetcode 1671 - Python • NeetCodeIO • 10,375 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