Leetcode 1766 Solution

This article provides solution to leetcode question 1766 (minimum-number-of-removals-to-make-mountain-array)

https://leetcode.com/problems/minimum-number-of-removals-to-make-mountain-array

Solution

class Solution: def lis(self, nums): ans = [] dp = []
for num in nums: l = 0 r = len(dp)
while l < r: m = (l + r) // 2 if dp[m] >= num: r = m else: l = m + 1
if l == len(dp): dp.append(num) else: dp[l] = num
ans.append(l + 1)
return ans
def minimumMountainRemovals(self, nums: List[int]) -> int: lis1 = self.lis(nums) lis2 = list(reversed(self.lis(list(reversed(nums)))))
opt = 0 for i in range(len(nums)): if lis1[i] == 1 or lis2[i] == 1: continue
opt = max(opt, lis1[i] + lis2[i] - 1) return len(nums) - opt