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.
Sample Example
Example 1:
Input: arr = [1, 3, 1]
Output: 0
Explanation: we do not need to remove any elements beacuse array itself is a mountain array.
Example 2:
Input: arr = [2,1,1,5,6,2,3,1]
Output: 3
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).
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.
For an efficient approach, you can refer to Minimum Number of Removals to Make Mountain Array - Part 2.
Algorithm
- Take all the inputs in the given format.
- Declare two arrays dpleft and dpright, to store LIS from left and right, respectively.
- Fill dpleft and dpright with LIS for each index, and this can be done with the DP solution of LIS.
- 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 we required result.