Minimum Number of Removals to Make Mountain Array

Leetcode Problem:

• Minimum Number of Removals to Make Mountain Array

Summary

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

Approach

• Dynamic programming approach to solve the problem
• Two arrays dp1 and dp2 are used to store the maximum number of elements that can be removed to make the left and right parts of the array a mountain array respectively.

Complexity

• O(n^2) where n is the size of the input array nums

Explanation

• The dp1 array is used to store the maximum number of elements that can be removed to make the left part of the array a mountain array
• The dp1 array is filled in a bottom-up manner
• For each element in the array, the maximum number of elements that can be removed to make the left part of the array a mountain array is updated
• The dp2 array is used to store the maximum number of elements that can be removed to make the right part of the array a mountain array
• The dp2 array is also filled in a bottom-up manner
• For each element in the array, the maximum number of elements that can be removed to make the right part of the array a mountain array is updated
• Finally, the minimum number of elements that need to be removed to make the entire array a mountain array is calculated by iterating over the array and checking if the current element is greater than or equal to the previous element
• If it is, then the minimum number of elements that need to be removed is updated.

Solution Code:

class Solution {
public:
    int dp1[1001];
    int dp2[1001];
    int minimumMountainRemovals(vector& nums) {
        int N = nums.size();
        dp1[N - 1] = 1;
        for(int i = N-2; i>= 0; i--){
            dp1[i] = 1;
            for(int j = i + 1; j < N; j++){
                if(nums[j]< nums[i]){
                    dp1[i] = max(dp1[i], dp1[j] + 1);
                }
            }
        }

        dp2[0] = 1;
        for(int i = 1 ; i < nums.size(); i++){
            dp2[i] = 1;
            for(int j = i -1; j >= 0; j--){
                if(nums[j]< nums[i]){
                    dp2[i] = max(dp2[i], dp2[j] + 1);
                }
            }
        }
        int res = 0;
        for(int i = 1 ; i< N-1; i++){
            if(nums[i-1] >= nums[i]) continue;
            int j_max = 0;
            bool success = false;
            for(int j = i + 1; j < N; j++){
                if(nums[i] <= nums[j]){
                    continue;
                }
                success = true;
                j_max = max(j_max, dp1[j]);
            }
            if (success)
                res = max(res, j_max + dp2[i]);
        }
        return N -res;
    }
};