# Question

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) with 0 < i < arr.length - 1 such that: arr < arr < … < 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]. Example 3:

Input: nums = [4,3,2,1,1,2,3,1] Output: 4 Example 4:

Input: nums = [1,2,3,4,4,3,2,1] Output: 1

Constraints:

3 <= nums.length <= 1000 1 <= nums[i] <= 109 It is guaranteed that you can make a mountain array out of nums.

# Algorithm-1

Here, we need to consider two directions.So, in the code, we scan twice, from left to right and from right to left. The only thing needs to be careful is that, when we calculate the final answer, we can’t count the first element (0 index) and the last element because it’s never a mountain if our peak is at that position.

C++

# Algorithm-2

### Code-2

Java

Java

class Solution {
public int minimumMountainRemovals(int[] nums) {
int length = nums.length;
int[] prevIndices = new int[length];
int[] nextIndices = new int[length];
Deque<Integer> stack = new LinkedList<Integer>();
stack.push(-1);
for (int i = 0; i < length; i++) {
int num = nums[i];
while (stack.size() > 1 && num <= nums[stack.peek()])
stack.pop();
prevIndices[i] = stack.peek();
stack.push(i);
}
stack = new LinkedList<Integer>();
stack.push(length);
for (int i = length - 1; i >= 0; i--) {
int num = nums[i];
while (stack.size() > 1 && num <= nums[stack.peek()])
stack.pop();
nextIndices[i] = stack.peek();
stack.push(i);
}
int[] maxIncrease = new int[length];
Arrays.fill(maxIncrease, 1);
int[] maxDecrease = new int[length];
Arrays.fill(maxDecrease, 1);
for (int i = 0; i < length; i++) {
if (prevIndices[i] >= 0) {
int num = nums[i];
for (int j = prevIndices[i]; j >= 0; j--) {
if (nums[j] < num)
maxIncrease[i] = Math.max(maxIncrease[i], maxIncrease[j] + 1);
}
}
}
for (int i = length - 1; i >= 0; i--) {
if (nextIndices[i] < length) {
int num = nums[i];
for (int j = nextIndices[i]; j < length; j++) {
if (nums[j] < num)
maxDecrease[i] = Math.max(maxDecrease[i], maxDecrease[j] + 1);
}
}
}
int maxLength = 0;
for (int i = 0; i < length; i++) {
if (maxIncrease[i] > 1 && maxDecrease[i] > 1) {
int curLength = maxIncrease[i] + maxDecrease[i] - 1;
maxLength = Math.max(maxLength, curLength);
}
}
return length - maxLength;
}
}