Longest Increasing Subsequence

Signal

"Longest valid chain so far, order matters but elements can be skipped" is the longest-increasing-subsequence shape. The naive DP (best chain ending at each index) is O(n²); if you need better, you're looking for a way to track possible chain endings without comparing every pair.

Approach

Maintain a tails array where tails[k] is the smallest possible tail value of any increasing subsequence of length k + 1 seen so far. For each new number, binary-search tails for where it belongs: if it extends the longest chain, append it; otherwise, replace the first tail that's >= it, since a smaller tail at that length keeps future extensions easier. The final length of tails is the answer.

Skeleton

tails = []
for x in nums:
    i = bisect_left(tails, x)
    if i == len(tails): tails.append(x)
    else: tails[i] = x
return len(tails)

Solution

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)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

Complexity

O(n log n) time — one binary search per element. O(n) space for tails.

Pitfalls

• tails is not an actual longest increasing subsequence by the end — it's overwritten as better options appear. It only tracks lengths correctly; don't try to read the subsequence itself off of it.
• The O(n²) DP (dp[i] = longest chain ending at i, comparing to every j < i) is the natural first idea and is worth naming, but isn't the Solution shipped here — lead with bisect_left for the O(n log n) version.
• Use bisect_left (not bisect_right) to keep the subsequence strictly increasing — bisect_right would allow equal elements to extend the chain.