BinarySearch 0538 Bus Stop

Problem statement

https://binarysearch.com/problems/Bus-Stop/

Solution

What is actually we need to find is the longest not-increasing subsequence: we can reverse nums and look for not-decreasing subsequence: we can use classical approach, but change bisect_left with `bisect.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, nums):
        def LIS(nums):
            dp = [10**10] * (len(nums) + 1)
            for elem in nums: dp[bisect.bisect(dp, elem)] = elem  
            return dp.index(10**10)

        return LIS(nums[::-1])