<filename>python3/longest_increasing_subsequence.py
from bisect import bisect_left

# Space : O(n)
# Time  : O(n log n)


class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        sub = []
        for num in nums:
            i = bisect_left(sub, num)
            if i == len(sub):
                sub.append(num)
            else:
                sub[i] = num
        return len(sub)

<filename>python3/longest_increasing_subsequence.py
from bisect import bisect_left

# Space : O(n)
# Time  : O(n log n)


class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        sub = []
        for num in nums:
            i = bisect_left(sub, num)
            if i == len(sub):
                sub.append(num)
            else:
                sub[i] = num
        return len(sub)

# Space : O(n) # Time  : O(n log n)