Leetcode Daily Question 30/10/2024 - 1671. Minimum Number of Removals to Make Mountain Array

Problem Description:

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.

from typing import List
class Solution:
  def minimumMountainRemovals(self, nums: List[int]) -> int:
    def LIS(seq: List[int]) -> List[int]:
      n = len(seq)
      LIS = [0] * n
      tails = []
      
      for i in range(n):
        num = seq[i]
        index = bisect.bisect_left(tails,num)
        if index == len(tails):
          tails.append(num)
        else:
          tails[index] = num
        LIS[i] = index + 1
      
      return LIS
    
  
    left_LIS = LIS(nums)
    right_LIS = LIS(nums[::-1])[::-1]
    max_len = 0
    
    for i in range(1, len(nums) - 1):
      if left_LIS[i] > 1 and right_LIS[i] > 1:
        max_len = max(max_len, left_LIS[i] + right_LIS[i] - 1)
        
    return len(nums) - max_len

Explanation:

We can solve this by finding the longest increasing subsequence from start to the peak, and the longest decreasing subsequence from peak to the end. The total length of the nums array minus the length of this increasing/ decreasing subsequence gives the number of removals needed.

To calculate the longest increasing subsequence, we can use binary search. The idea is to build the longest subsequence by considering where the next num could be placed.

We keep a tails array and append num if it is greater than all existing number in tails, or replacing num at the insertion point (found using binary search) for a smaller num to have a better chance of extending the subsequence.

def LIS(seq: List[int]) -> List[int]:
      n = len(seq)
      LIS = [0] * n
      tails = []
      
      for i in range(n):
        num = seq[i]
        index = bisect.bisect_left(tails,num)
        if index == len(tails):
          tails.append(num)
        else:
          tails[index] = num
        LIS[i] = index + 1
      
      return LIS

To make nums into a mountain array, we also need to find the LDS to the right of the peak. This is the same as finding LIS of the reverse of nums.

Since we do not know where the peak should be, we calculate the desired LIS/ LDS combination by considering each position in nums to be the peak.

To avoid repeated calculation, we intrinsically calculate the LIS for each position in nums (left to right) and LIS for each position in nums reversed (right to left).

Then the desired LIS/ LDS combination is left_LIS[i] + right_LIS[i] - 1 for each i where 0 <= i < len(nums)

left_LIS = LIS(nums)
right_LIS = LIS(nums[::-1])[::-1]
max_len = 0
    
for i in range(1, len(nums) - 1):
  if left_LIS[i] > 1 and right_LIS[i] > 1:
    max_len = max(max_len, left_LIS[i] + right_LIS[i] - 1)
        
return len(nums) - max_len

The time complexity is O(n log n). Since each binary search operation takes O(log n) time and we do this for each subarray ending in position i, 0 <= i < len(seq), we obtain O(n log n) time for calculating LIS. Since we calculate LIS from left to right and right to left, the total time complexity is O(2n log n) ≈ O( n log n).

The space complexity is O(n) since we need to store information LIS ending each each position in nums.

The full solution can be found near the top of the page.