## Similar Problems

Similar Problems not available

# Minimum Number Of Removals To Make Mountain Array - Leetcode Solution

## Companies:

LeetCode: Minimum Number Of Removals To Make Mountain Array Leetcode Solution

Difficulty: Hard

Topics: greedy dynamic-programming binary-search array

Problem Statement:

A mountain array is defined as an array that: - Has at least 3 elements. - Has an element with the largest value called the "peak", which is the maximum element in the array and this element appears on at least two contiguous indices in the array. - Has elements on both sides of the peak that are strictly increasing up to the peak.

Given an integer array nums, you need to return the minimum number of elements to remove to make nums a mountain array.

Solution:

Approach: We can use a greedy approach while identifying the peak and the ascending portions of the mountain array. Once we identify the peak, we can count the number of elements on the left and right sides that are part of the ascending sequence. If the total length of the ascending sequence is less than 3, we cannot make a mountain array. Otherwise, we can calculate the number of elements to be removed by subtracting the length of the ascending sequence from the length of the array.

Steps:

- Loop through the array to find the peak element.
- If a peak is not found, return -1 as it is not possible to form a mountain array.
- Once a peak element is found, we can divide the array into two parts - left and right.
- Count the length of the ascending sequence on the left and right sides of the peak.
- If either the left or the right side has an ascending sequence of length less than 1, return -1 as it is not possible to form a mountain array.
- Otherwise, return the length of the array minus the length of the ascending sequence.
- Done.

Implementation:

def minimumMountainRemoval(A): n = len(A) peak = -1 for i in range(1, n-1): if A[i] > A[i-1] and A[i] > A[i+1]: peak = i break

```
if peak == -1:
return -1
left, right = peak, peak
while left > 0 and A[left-1] < A[left]:
left -= 1
while right < n-1 and A[right] > A[right+1]:
right += 1
if left == peak or right == peak:
return -1
return (n - (right - left + 1))
```

# Sample Test Case

print(minimumMountainRemoval([2,1,1,5,6,2,3,1])) # Expected Output: 3

# Time Complexity: O(n)

# Space Complexity: O(1)

## Minimum Number Of Removals To Make Mountain Array Solution Code

`1`