1671. Minimum Number of Removals to Make Mountain Array LeetCode Solution

In this guide, you will get 1671. Minimum Number of Removals to Make Mountain Array LeetCode Solution with the best time and space complexity. The solution to Minimum Number of Removals to Make Mountain Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Number of Removals to Make Mountain Array solution in C++
Minimum Number of Removals to Make Mountain Array solution in Java
Minimum Number of Removals to Make Mountain Array solution in Python
Additional Resources

1671. Minimum Number of Removals to Make Mountain Array LeetCode Solution image

Problem Statement of Minimum Number of Removals to Make Mountain Array

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 + 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] <= 109
It is guaranteed that you can make a mountain array out of nums.

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n)

1671. Minimum Number of Removals to Make Mountain Array LeetCode Solution in C++

class Solution {
 public:
  int minimumMountainRemovals(vector<int>& nums) {
    const vector<int> l = lengthOfLIS(nums);
    const vector<int> r = reversed(lengthOfLIS(reversed(nums)));
    int maxMountainSeq = 0;

    for (int i = 0; i < nums.size(); ++i)
      if (l[i] > 1 && r[i] > 1)
        maxMountainSeq = max(maxMountainSeq, l[i] + r[i] - 1);

    return nums.size() - maxMountainSeq;
  }

 private:
  // Similar to 300. Longest Increasing Subsequence
  vector<int> lengthOfLIS(vector<int> nums) {
    // tails[i] := the minimum tail of all the increasing subsequences having
    // length i + 1
    vector<int> tails;
    // dp[i] := the length of LIS ending in nums[i]
    vector<int> dp;
    for (const int num : nums) {
      if (tails.empty() || num > tails.back())
        tails.push_back(num);
      else
        tails[firstGreaterEqual(tails, num)] = num;
      dp.push_back(tails.size());
    }
    return dp;
  }

  int firstGreaterEqual(const vector<int>& arr, int target) {
    return ranges::lower_bound(arr, target) - arr.begin();
  }

  vector<int> reversed(const vector<int>& nums) {
    return {nums.rbegin(), nums.rend()};
  }
};
/* code provided by PROGIEZ */

1671. Minimum Number of Removals to Make Mountain Array LeetCode Solution in Java

class Solution {
  public int minimumMountainRemovals(int[] nums) {
    int[] l = lengthOfLIS(nums);
    int[] r = reversed(lengthOfLIS(reversed(nums)));
    int maxMountainSeq = 0;

    for (int i = 0; i < nums.length; ++i)
      if (l[i] > 1 && r[i] > 1)
        maxMountainSeq = Math.max(maxMountainSeq, l[i] + r[i] - 1);

    return nums.length - maxMountainSeq;
  }

  // Similar to 300. Longest Increasing Subsequence
  private int[] lengthOfLIS(int[] nums) {
    // tails[i] := the minimum tail of all the increasing subsequences with
    // length i + 1
    List<Integer> tails = new ArrayList<>();
    // dp[i] := the length of LIS ending in nums[i]
    int[] dp = new int[nums.length];
    for (int i = 0; i < nums.length; ++i) {
      final int num = nums[i];
      if (tails.isEmpty() || num > tails.get(tails.size() - 1))
        tails.add(num);
      else
        tails.set(firstGreaterEqual(tails, num), num);
      dp[i] = tails.size();
    }
    return dp;
  }

  private int firstGreaterEqual(List<Integer> arr, int target) {
    final int i = Collections.binarySearch(arr, target);
    return i < 0 ? -i - 1 : i;
  }

  private int[] reversed(int[] nums) {
    int[] arr = nums.clone();
    int l = 0;
    int r = nums.length - 1;
    while (l < r)
      swap(arr, l++, r--);
    return arr;
  }

  private void swap(int[] arr, int i, int j) {
    final int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}
// code provided by PROGIEZ

1671. Minimum Number of Removals to Make Mountain Array LeetCode Solution in Python

class Solution:
  def minimumMountainRemovals(self, nums: list[int]) -> int:
    left = self._lengthOfLIS(nums)
    right = self._lengthOfLIS(nums[::-1])[::-1]
    maxMountainSeq = 0

    for l, r in zip(left, right):
      if l > 1 and r > 1:
        maxMountainSeq = max(maxMountainSeq, l + r - 1)

    return len(nums) - maxMountainSeq

  # Similar to 300. Longest Increasing Subsequence
  def _lengthOfLIS(self, nums: list[int]) -> list[int]:
    # tails[i] := the minimum tail of all the increasing subsequences having
    # length i + 1
    tails = []
    # dp[i] := the length of LIS ending in nums[i]
    dp = []
    for num in nums:
      if not tails or num > tails[-1]:
        tails.append(num)
      else:
        tails[bisect.bisect_left(tails, num)] = num
      dp.append(len(tails))
    return dp
 # code by PROGIEZ