1671. Minimum Number of Remo...
This page provides solutions for the leetcode problem 1671. Minimum Number of Removals to Make Mountain Array.
Problem Explanation
The problem requires us to calculate minimum number of elements to remove to make input array a mountain array.
An array is a mountain array if and only if:
- There exists some index (-indexed) with such that:
Solution
This problem can be solved using the Dynamic Programming. More such problem can be found here.
- Java
class Solution {
public int minimumMountainRemovals(int[] nums) {
int n = nums.length;
int[] dpLeft = new int[n];
for(int i = 1; i < n; i++) {
for(int j = 0; j < i; j++) {
if(nums[j] < nums[i]) {
dpLeft[i] = Math.max(dpLeft[i], dpLeft[j] + 1);
}
}
}
int[] dpRight = new int[n];
for(int i = n - 2; i >= 0; i--) {
for(int j = n - 1; j > i; j--) {
if (nums[j] < nums[i]) {
dpRight[i] = Math.max(dpRight[i], dpRight[j] + 1);
}
}
}
int max = 0;
for(int i = 1; i < n - 1; i++) {
if (dpLeft[i] > 0 && dpRight[i] > 0) {
max = Math.max(max, dpLeft[i] + dpRight[i] + 1);
}
}
return n - max;
}
}
Complexity
Let be the length of the input array
Time Complexity
Each of the indices in the input array is visited only once, so time complexity will be:
Space Complexity
Solution uses space for storing longest increasing sequence from right and left, so space complexity will be: