Problem

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[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.

Examples

Example 1:

1
2
3

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:

1
2
3

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].

Solution

Method 1 - Using Longest Increasing Sequence

To solve the problem of converting an array nums into a mountain array with the minimum number of deletions, we need to identify the longest mountain subsequence within the array and then compute the number of deletions required to achieve it.

Here are the steps:

  1. Use dynamic programming to find the length of the longest increasing subsequence (LIS) up to each index i.
  2. Use dynamic programming to find the length of the longest decreasing subsequence (LDS) from each index i.
  3. Combine results from steps 1 and 2 to find a peak i such that both the increasing sequence up to i and the decreasing sequence starting from i are maximized.
  4. The number of deletions required will be the total length of the array minus the length of the longest mountain subsequence.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

class Solution {
    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length;
        int[] lis = new int[n];
        int[] lds = new int[n];

        // Find LIS for each element
        for (int i = 0; i < n; i++) {
            lis[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    lis[i] = Math.max(lis[i], lis[j] + 1);
                }
            }
        }

        // Find LDS for each element
        for (int i = n - 1; i >= 0; i--) {
            lds[i] = 1;
            for (int j = n - 1; j > i; j--) {
                if (nums[i] > nums[j]) {
                    lds[i] = Math.max(lds[i], lds[j] + 1);
                }
            }
        }

        // Find the maximum length of mountain array
        int ans = Integer.MAX_VALUE;
        for (int i = 1; i < n - 1; i++) {
            if (lis[i] > 1 && lds[i] > 1) { // Peak must be valid
                ans = Math.min(ans, n - (lis[i] + lds[i] - 1));
            }
        }

        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution:
    def minimumMountainRemovals(self, nums: List[int]) -> int:
        n = len(nums)
        lis: List[int] = [1] * n
        lds: List[int] = [1] * n
        
        # Find LIS for each element
        for i in range(n):
            for j in range(i):
                if nums[i] > nums[j]:
                    lis[i] = max(lis[i], lis[j] + 1)
        
        # Find LDS for each element
        for i in range(n-1, -1, -1):
            for j in range(n-1, i, -1):
                if nums[i] > nums[j]:
                    lds[i] = max(lds[i], lds[j] + 1)
        
        # Find the maximum length of mountain array
        ans: int = float('inf')
        for i in range(1, n-1):
            if lis[i] > 1 and lds[i] > 1:  # Peak must be valid
                ans = min(ans, n - (lis[i] + lds[i] - 1))
        
        return ans

Complexity

  • ⏰ Time complexity: O(n^2), due to the nested loops in the dynamic programming approach.
  • 🧺 Space complexity: O(n) for the LIS and LDS arrays.