Introduction
In this article, we will discuss a very good problem: 'Minimum number of removals to make a mountain array.'
Mountain array is an array where,
There exists some index i with 0 < i < arr.size - 1 where,
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
Problem Statement
Given an integer array arr, return the minimum number of elements to remove to make arr a mountain array.
Constraints:
- 3 <= arr.length <= 1000
- 1 <= arr[i] <= 109
- It is guaranteed that you can make a mountain array out of arr.
Sample Examples
Example 1:
Input: arr = [1, 3, 1]
Output: 0
Explanation: we do not need to remove any elements because the array itself is a mountain array.
Example 2:
Input: arr = [2,1,1,5,6,2,3,1]
Output: 0
Explanation: Remove the elements at indices 0, 1, and 5, making the array arr = [1,5,6,3,1].
Approach
The basic idea to solve this problem will be to find the longest mountain subsequence first then remove it from the total number of elements of an array.
Therefore the number of removals = Total length of given array- (longest mountain subsequence).
To calculate the longest mountain subsequence, first, calculate the longest increasing subsequence from left for each index and store it in an array(say, dpleft). Similarly, calculate the longest increasing subsequence from left for each index and store it in an array(say, dpright). In this efficient approach, dpleft and dpright can be filled in better time complexity (nlogn). You can also see N^2 approach of the given problem.
Now consider each 0<i<n to be the middle of a mountain subsequence with the length of subsequence as dpleft[i]+dright[i]-1 (we subtract 1 to not double count the middle element).
However, we will check for i only if dpleft[i]>1 and dpright[i]>1 because the sequence is not a mountain sequence, and removing conditions can give inconsistent results if either dpleft[i] or dpright[i] = 1, then it means that the sequence is either strictly increasing or decreasing.
Steps of Algorithm
- Take all the inputs in the given format.
- Declare two arrays dpleft and dpright to store LIS from left and right, respectively.
- Declare a temporary vector lis, which will help in filling dpleft and dpright.
- Fill dpleft LIS for each index, and this can be done with the DP solution of LIS.
- While filling the dpleft we will use a lower_bound()/binary search function to search for elements in the lis vector and then update the vector accordingly.
- If the element is not present in lis vector and greater than the last element, insert it at the end.
- Else use lower bound/binary search for the element then update the element in lis, which is just greater or equal to the current element of the array.
- Reverse the original array.
- Fill dpright using the same logic.
- Then traverse each index of the array, and check the length of the maximum mountain array for each index.
- Length of each mountain array will be, dpleft[i]+dright[i]-1 , after checking condition only if dpleft[i]>1 and dpright[i]>1.
- Store max_length in variable and keep updating it accordingly.
- Output N - max_length that will be the required result.
Must Read Lower Bound in C++