Leetcode 1671. Minimum Number of Removals to Make Mountain Array

Problem Explanation

The goal of the problem is to transform a given array into a mountain array by removing the minimum number of elements. An array is defined as a mountain array when it strictly increases up to a point and then strictly decreases, given that:

• The array’s 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] and arr[i] > arr[i + 1] > ... > arr[arr.length - 1].

A basic approach would be to iterate through the array and locate where such a condition can be established. The sections of the array that are strictly increasing and strictly decreasing can be considered as separate Longest Increasing Subsequences (LIS).

The length of the longest subsequence that can form a mountain array is calculated for each element. Once these sequences are found, the minimum number of elements that need to be removed can be obtained by subtracting the maximum length of the mountain from the original length of the array.

For Example:

Let's take an example: nums = [4,3,2,1,1,2,3,1] We can see that we can make a mountain array by removing the first 4 elements. Then, our mountain array will be [1,2,3,1] with a length of 4. Hence the output here will be 4.

Python Solution

1
2python
3import bisect
4class Solution:
5    def minimumMountainRemovals(self, nums: List[int]) -> int:
6        n = len(nums)
7        left_dp = [0]*n
8        right_dp = [0]*n
9        left_nums = []
10        right_nums = []
11        res = float('inf')   
12             
13        for i, num in enumerate(nums):
14            if left_nums and num != left_nums[-1]:
15                idx = bisect.bisect(left_nums, num)
16                if idx == len(left_nums):
17                    left_nums.append(num)
18                else:
19                    left_nums[idx] = num
20            elif not left_nums:
21                left_nums.append(num)
22            left_dp[i] = len(left_nums)
23
24        for i in range(n-1, -1, -1):
25            num = nums[i]
26            if right_nums and num != right_nums[-1]:
27                idx = bisect.bisect(right_nums, num)
28                if idx == len(right_nums):
29                    right_nums.append(num)
30                else:
31                    right_nums[idx] = num
32            elif not right_nums:
33                right_nums.append(num)
34            right_dp[i] = len(right_nums)
35        
36        for i in range(1, n-1):
37            if left_dp[i]>1 and right_dp[i]>1:
38                res = min(res, n - (left_dp[i]+right_dp[i]-1))
39
40        return res

Java Solution

1
2java
3import java.util.*;
4class Solution {
5    public int minimumMountainRemovals(int[] nums) {
6        int n = nums.length;
7        int[] left = new int[n];
8        int[] right = new int[n];
9        Arrays.fill(left, 1);
10        Arrays.fill(right, 1);
11        for(int i = 1; i < n; i++) {
12            for(int j = 0; j < i; j++) {
13                if(nums[i] > nums[j]) {
14                    left[i] = Math.max(left[i], left[j] + 1);
15                }
16            }
17        }
18        for(int i = n - 2; i >= 0; i--) {
19            for(int j = n - 1; j > i; j--) {
20                if(nums[i] > nums[j]) {
21                    right[i] = Math.max(right[i], right[j] + 1);
22                }
23            }
24        }
25        int res = n;
26        for(int i = 1; i < n - 1; i++) {
27            if(left[i] > 1 && right[i] > 1) {
28                res = Math.min(res, n - (left[i] + right[i] - 1));
29            }
30        }
31        return res;
32    }
33}

We shall be updating python and java solutions. For now, you practice on these.

Explanation related to solution

In both Java and Python scripts, the concept is the same. Both scripts first attempt to create two arrays capturing the lengths of the longest increasing subsequences from both ends, then iterate through the values. Finally, the size of the longest mountain subsequence is calculated and subtracted from the length of the original array. In Java, Arrays.fill is used to initially fill up the arrays, while a list comprehension is used in Python.## JavaScript Solution

In JavaScript, it can be solved in the following way:

1
2javascript
3var minimumMountainRemovals = function(nums) {
4    let n = nums.length;
5    let left = new Array(n).fill(1);
6    let right = new Array(n).fill(1);
7    
8    for(let i = 1; i < n; i++) {
9        for(let j = 0; j < i; j++) {
10            if(nums[i] > nums[j]) {
11                left[i] = Math.max(left[i], left[j] + 1);
12            }
13        }
14    }
15    
16    for(let i = n - 2; i >= 0; i--) {
17        for(let j = n - 1; j > i; j--) {
18            if(nums[i] > nums[j]) {
19                right[i] = Math.max(right[i], right[j] + 1);
20            }
21        }
22    }
23
24    let res = n;
25    for(let i = 1; i < n - 1; i++) {
26        if(left[i] > 1 && right[i] > 1) {
27            res = Math.min(res, n - (left[i] + right[i] - 1));
28        }
29    }
30    
31    return res;
32};

Explanation related to solution

This JavaScript solution follows the same logic as the Python and Java solutions above. The algorithm first initializes two arrays, left and right, to keep track of the longest increasing subsequences from both ends.

The for loops iterate through the nums array to calculate the length of these increasing subsequences. If the current number is greater than the previous one, it's part of an increasing subsequence, and the script updates the corresponding index in the left or right array.

In the final for loop, the script checks every element of the array to see if it could be the highest point of a mountain (i.e., if there are increasing subsequences on both sides). If so, it calculates the length of that potential mountain and updates the result to be the smallest required number of removals found so far.

The main difference from the Python and Java Solutions is how arrays are being filled up initially in JavaScript, which uses the fill method, compared to the Arrays.fill method in Java and Python's list comprehension.

Now, you have the solutions in Python, Java, and JavaScript. Try practicing them in your preferred language to better understand the underlying logic and to improve your problem-solving skills.