1671. Minimum Number of Removals to Make Mountain Array.md

1671. Minimum Number of Removals to Make Mountain Array

---

the last one in Biweekly Contest 40.

---

Difficulty : Hard

Related Topics : DynamicProgramming

---

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

Example 3:

Input: nums = [4,3,2,1,1,2,3,1]
Output: 4

Example 4:

Input: nums = [1,2,3,4,4,3,2,1]
Output: 1

Constraints:

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

---

same as 300. Longest Increasing Subsequence.

---

Solution

• mine
  • Java

    • Runtime: 49 ms, faster than 80.00%, Memory Usage: 39.5 MB, less than 80.00% of Java online submissions

      // O(N^2)time
      // O(N)space
      public int minimumMountainRemovals(int[] nums) {
          int[] dpL = leftToRight(nums);
          int[] dpR = rightToLeft(nums);
          int n = nums.length;
          int res = n;
          for(int i = 1; i < n - 1; i++){
              if(dpL[i] <= 1 || dpR[i] <= 1) continue;
      
              res = Math.min(res, n - dpL[i] - dpR[i] + 1);
          }
          return res;
      }
      
      int[] leftToRight(int[] nums){
          int n = nums.length;
          int[] dp = new int[n];
          Arrays.fill(dp, 1);
          for(int i = 1; i < n; i++){
              for(int j = 0; j < i; j++){
                  if(nums[j] < nums[i]){
                      dp[i] = Math.max(dp[i], dp[j] + 1);
                  }
              }
          }
          return dp;
      }
      
      int[] rightToLeft(int[] nums){
          int n = nums.length;
          int[] dp = new int[n];
          Arrays.fill(dp, 1);
          for(int i = n - 2; i >= 0; i--){
              for(int j = n - 1; j > i; j--){
                  if(nums[j] < nums[i]){
                      dp[i] = Math.max(dp[i], dp[j] + 1);
                  }
              }
          }
          return dp;
      }
      

    • DP & Binary Search Runtime: 5 ms, faster than 100.00%, Memory Usage: 39.2 MB, less than 100.00% of Java online submissions

      // O(N * logN)time
      // O(N)space
      public int minimumMountainRemovals(int[] nums) {
          int[] left = dp(nums);
          reverse(nums);
          int[] right = dp(nums);
      
          int n = nums.length;
          int res = n;
          for (int i = 0; i < n; i++) {
              if (left[i] <= 1 || right[n - 1 - i] <= 1) continue;
      
              res = Math.min(res, n - left[i] - right[n - 1 - i] + 1);
          }
          return res;
      }
      
      int[] dp(int[] nums) {
          int n = nums.length;
          int[] dp = new int[n];
          int[] count = new int[n];
          int size = 0;
          for (int i = 0; i < n; i++) {
              int l = 0, r = size;
              while (l != r) {
                  int mid = (l + r) >>> 1;
                  if (dp[mid] < nums[i]) {
                      l = mid + 1;
                  } else {
                      r = mid;
                  }
              }
              dp[l] = nums[i];
              if (l == size) size++;
              count[i] = size;
          }
          return count;
      }
      
      void reverse(int[] nums) {
          int n = nums.length;
          for (int i = 0; i < n; i++) {
              if (i >= n - 1 - i) break;
      
              int t = nums[i];
              nums[i] = nums[n - 1 - i];
              nums[n - 1 - i] = t;
          }
      }
      

---