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

Approach 01:

class Solution {
public:
    int minimumMountainRemovals(vector<int>& nums) {
        const vector<int> leftLIS = calculateLIS(nums);
        const vector<int> rightLIS = reverseVector(calculateLIS(reverseVector(nums)));
        int maxMountainSequence = 0;

        for (int i = 0; i < nums.size(); ++i)
            if (leftLIS[i] > 1 && rightLIS[i] > 1)
                maxMountainSequence = max(maxMountainSequence, leftLIS[i] + rightLIS[i] - 1);

        return nums.size() - maxMountainSequence;
    }

private:
    // Helper function for Longest Increasing Subsequence
    vector<int> calculateLIS(vector<int> nums) {
        vector<int> tails;
        vector<int> lisLengths;
        for (const int num : nums) {
            if (tails.empty() || num > tails.back())
                tails.push_back(num);
            else
                tails[findFirstGreaterOrEqual(tails, num)] = num;
            lisLengths.push_back(tails.size());
        }
        return lisLengths;
    }

    int findFirstGreaterOrEqual(const vector<int>& sequence, int target) {
        return lower_bound(sequence.begin(), sequence.end(), target) -
               sequence.begin();
    }

    vector<int> reverseVector(const vector<int>& nums) {
        return {nums.rbegin(), nums.rend()};
    }
};

class Solution:
    def minimumMountainRemovals(self, nums):
        leftLIS = self.calculateLIS(nums)
        rightLIS = self.calculateLIS(self.reverseList(nums))[::-1]
        maxMountainSequence = 0

        for i in range(len(nums)):
            if leftLIS[i] > 1 and rightLIS[i] > 1:
                maxMountainSequence = max(maxMountainSequence, leftLIS[i] + rightLIS[i] - 1)

        return len(nums) - maxMountainSequence

    # Helper function for Longest Increasing Subsequence
    def calculateLIS(self, nums):
        tails = []
        lisLengths = []
        for num in nums:
            if not tails or num > tails[-1]:
                tails.append(num)
            else:
                tails[self.findFirstGreaterOrEqual(tails, num)] = num
            lisLengths.append(len(tails))
        return lisLengths

    def findFirstGreaterOrEqual(self, sequence, target):
        low, high = 0, len(sequence)
        while low < high:
            mid = (low + high) // 2
            if sequence[mid] >= target:
                high = mid
            else:
                low = mid + 1
        return low

    def reverseList(self, nums):
        return nums[::-1]

Time Complexity

• Calculating Left and Right Longest Increasing Subsequences (LIS):

  The calculateLIS function is called twice: once for the original array and once for its reverse. Each call to calculateLIS has a time complexity of \(O(n \log n)\) due to the binary search operation in findFirstGreaterOrEqual, where n is the size of the array.

• Maximum Mountain Sequence Calculation:

  The loop through each element in nums to find the maximum mountain sequence has a complexity of \(O(n)\).

• Overall Time Complexity:

  Since the primary operations are dominated by the two LIS calculations, the total time complexity is \(O(n \log n)\).

Space Complexity

• Left and Right LIS Storage:

  Each LIS calculation produces a vector of size \(O(n)\), resulting in two \(O(n)\) vectors to store leftLIS and rightLIS.

• Tails Array in calculateLIS:

  The temporary tails array used during each LIS computation is also of size \(O(n)\).

• Auxiliary Space:

  Additional small, constant space is used for the helper functions and variables.

• Overall Space Complexity:

  The space complexity is \(O(n)\).