1671. Minimum Number of Removals to Make Mountain Array
Difficulty: Hard
Topics: Array
, Binary Search
, Dynamic Programming
, Greedy
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) with0 < 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.
Hint:
- Think the opposite direction instead of minimum elements to remove the maximum mountain subsequence
- Think of LIS it's kind of close
Solution:
We can use a dynamic programming approach with the idea of finding the maximum mountain subsequence rather than directly counting elements to remove. This approach is based on finding two Longest Increasing Subsequences (LIS) for each position in the array: one going left-to-right and the other going right-to-left. Once we have the longest possible mountain subsequence, the difference between the original array length and this subsequence length will give us the minimum elements to remove.
Solution Outline
-
Identify increasing subsequence lengths:
- Compute the
leftLIS
array, whereleftLIS[i]
represents the length of the longest increasing subsequence ending ati
(going left to right).
- Compute the
-
Identify decreasing subsequence lengths:
- Compute the
rightLIS
array, whererightLIS[i]
represents the length of the longest decreasing subsequence starting ati
(going right to left).
- Compute the
-
Calculate maximum mountain length:
- For each index
i
where0 < i < n - 1
, check if there exists a valid peak (i.e.,leftLIS[i] > 1
andrightLIS[i] > 1
). Calculate the mountain length ati
asleftLIS[i] + rightLIS[i] - 1
.
- For each index
-
Get the minimum removals:
- The minimum elements to remove will be the original array length minus the longest mountain length found.
Let's implement this solution in PHP: 1671. Minimum Number of Removals to Make Mountain Array
<?php
/**
* @param Integer[] $nums
* @return Integer
*/
function minimumMountainRemovals($nums) {
...
...
...
/**
* go to ./solution.php
*/
}
// Example usage
$nums1 = [1, 3, 1];
echo minimumMountainRemovals($nums1); // Output: 0
$nums2 = [2, 1, 1, 5, 6, 2, 3, 1];
echo minimumMountainRemovals($nums2); // Output: 3
?>
Explanation:
-
Left LIS Calculation:
-
leftLIS[i]
stores the maximum length of an increasing subsequence ending ati
. We iterate through eachi
, and for eachi
, iterate from0
toi-1
to find the longest subsequence ending ati
.
-
-
Right LIS Calculation:
-
rightLIS[i]
stores the maximum length of a decreasing subsequence starting ati
. We iterate backward fromn-2
to0
, and for eachi
, iterate fromn-1
down toi+1
to find the longest subsequence starting ati
.
-
-
Mountain Calculation:
- A valid peak at index
i
must haveleftLIS[i] > 1
andrightLIS[i] > 1
. The length of a mountain with peak ati
isleftLIS[i] + rightLIS[i] - 1
.
- A valid peak at index
-
Final Calculation:
- The minimum removals needed is the difference between the original array length and the maximum mountain length found.
Complexity Analysis
- Time Complexity: O(n2), due to the double loop in the LIS calculations.
-
Space Complexity: O(n), for storing the
leftLIS
andrightLIS
arrays.
This solution ensures that we find the maximum mountain subsequence and compute the minimum removals required to achieve a mountain array.
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
Top comments (0)