Longest Increasing Subsequence

LeetCode 300 · View on LeetCode

O(n log n) patience sorting: maintain a list of smallest tail elements. Use binary search to find the position to replace or extend.

from bisect import bisect_left

def length_of_lis(nums: list[int]) -> int:
    tails = []
    for num in nums:
        pos = bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)

if __name__ == '__main__':
    print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 4
    print(length_of_lis([0, 1, 0, 3, 2, 3]))             # 4
    print(length_of_lis([7, 7, 7, 7]))                    # 1