300. Longest Increasing Subsequence

Medium

Python Solution

from bisect import bisect_left

class Solution:
    def lengthOfLIS(self, nums):

        sub = []
        for num in nums:
            i = bisect_left(sub, num) # find the right position to insert num
            if i == len(sub): # check if we are at right position or not. If yes, append num to sub. else, replace the value at i with num
                sub.append(num)
            else:
                sub[i] = num
        return len(sub)

Explanation

here bisect_left is used, to find the right position to insert num. bisect left uses binary search to find the right position. it works in left to right. as all the number in sub is in incresing order and right place, so it is will be the best case and time complexity will be O(nlogn).