Leetcode 1766 Solution

This article provides solution to leetcode question 1766 (minimum-number-of-removals-to-make-mountain-array)
Categories:
Tags:
Access this page by simply typing in "lcs 1766" in your browser address bar if you have bunnylol configured.

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