Longest Increasing Subsequence
Length of the longest strictly increasing subsequence (elements keep order, need not be adjacent).
Open on LeetCode ↗Intuition
Classic DP: dp[i] = length of the best increasing subsequence ending at i, built by scanning all smaller earlier elements. The O(n log n) upgrade keeps a list tails where tails[k] is the smallest possible tail of an increasing subsequence of length k+1 — each new number either extends the list or improves (lowers) one tail via binary search.
The O(n log n) version is worth recognising as a patience sorting problem: tails[i] is the smallest possible tail of any increasing subsequence of length i + 1. Keeping tails as small as possible leaves the most room to extend later, and because that array is sorted by construction you can binary search it. Whenever a DP array turns out to be monotone, a binary search can usually replace the inner loop.
Approach
O(n²) DP first
dp[i] = 1 + max(dp[j]) over all j < i with nums[j] < nums[i]. Answer is max(dp). Simple, and the base for many follow-up problems.
The tails insight
Among all increasing subsequences of length L, only the one with the smallest tail matters — it is the easiest to extend. So keep just that smallest tail per length: tails is sorted, enabling binary search.
Patience step
For each num: find the first tail ≥ num (bisect_left). If none, num extends the longest run (append). Otherwise it replaces that tail — same length, better (smaller) tail. Length of tails is the answer.
Solution & live demo
Common pitfalls
Reading tails as the actual subsequence
return tails # the LIS itself
return len(tails)
Only the length is meaningful. On [10, 9, 2, 5, 3, 7] the array ends as [2, 3, 7], which is a genuine LIS here, but on other inputs it holds tails from different subsequences that never coexisted. Reconstructing the real sequence needs separate predecessor tracking.
Using bisect_right instead of bisect_left
i = bisect_right(tails, x)
i = bisect_left(tails, x)
bisect_right places a duplicate after its equals, extending the run and counting a non-strict increase. For a strictly increasing subsequence, an equal value must replace its match, which is what bisect_left does. (Flip it deliberately when the problem asks for non-decreasing.)
Appending whenever the value is larger
if x > tails[-1]:
tails.append(x)
else:
tails[i] = xif i == len(tails):
tails.append(x)
else:
tails[i] = xThe two tests agree, but the i == len(tails) form derives the decision from the search you already paid for, and it doesn't crash on the first element when tails is still empty.
Edge cases
Every number replaces tails[0]; answer 1.
bisect_left makes equal values replace, not extend — enforcing strict increase.
Only its length is meaningful; elements may come from different subsequences.