1766. Minimum Number Of Removals To Make Mountain Array¶

Difficulty: Hard

1766. Minimum Number of Removals to Make Mountain Array

Hard

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.

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

Constraints:

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

Solution¶

class Solution {
    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length;
        return n - solve(nums);
    }

    public static int solve(int arr[]){
        int n = arr.length;
        int dp1[] = new int[n + 1];
        int dp2[] = new int[n + 2];
        Arrays.fill(dp1,1); Arrays.fill(dp2, 1);
        for(int ind = 0; ind < n; ind ++ ){
            for(int prev = 0; prev < ind; prev ++){
                if(arr[ind] > arr[prev]) dp1[ind] = Math.max(dp1[ind] , 1 + dp1[prev]);
            }
        }
        for(int ind = n -  1; ind >=0 ;ind --){
            for(int prev = n - 1; prev > ind; prev--){
                if(arr[ind] > arr[prev]) dp2[ind] = Math.max(dp2[ind] , 1 + dp2[prev]);
            }
        }
        int maxi = -1;
        for(int i = 0; i < n; i++){
            if(dp1[i] >= 2 && dp2[i] >= 2) maxi = Math.max(maxi, dp1[i] + dp2[i] - 1);
        }
        return maxi;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here