Problem 52 · Dynamic Programming

Longest Increasing Subsequence (O(n log n))

MediumClassic DSA & systems

01Problem

Given an integer array, return the length of the longest strictly increasing subsequence.

02Key insight

Patience sorting: tails[i] holds the smallest tail of any increasing subsequence of length i+1. tails stays sorted, so each element binary-searches its slot.

03Solution

solution.pypython11 lines

from bisect import bisect_left

def length_of_lis(nums: list[int]) -> int:
    tails: list[int] = []
    for x in nums:
        i = bisect_left(tails, x)  # bisect_left => strictly increasing
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

Try it first.

TimeO(n log n)

SpaceO(n)

tests.py · 4 passing

tests.pypython4 lines

assert length_of_lis([10,9,2,5,3,7,101,18]) == 4
assert length_of_lis([]) == 0
assert length_of_lis([7,7,7]) == 1
assert length_of_lis([0,1,0,3,2,3]) == 4

04Staff-level follow-up

Need the actual subsequence, not just length? Store the index at each tails slot plus a predecessor array, then backtrack from the last tail.