Longest Increasing Subsequence
Find the longest rising subsequence, first with the O(n²) table and then with the binary-search trick that makes it O(n log n)
Problem Statement
Given an integer array, return the length of the longest strictly increasing subsequence.
A subsequence keeps the original order but may skip elements. It does not have to be contiguous.
Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
Why: [2, 3, 7, 101] or [2, 3, 7, 18]
Input: nums = [0, 1, 0, 3, 2, 3]
Output: 4
Why: [0, 1, 2, 3]Intuition
Subsequences may skip elements, so a list of n numbers has 2ⁿ subsequences. Checking all of them is hopeless for anything but tiny inputs.
The key insight
Do not ask "what is the longest increasing subsequence?" — that requires seeing the whole array at once.
Ask instead: "what is the longest increasing subsequence that ENDS at position i?"
Pinning the ending down makes the question answerable from what came before. A subsequence ending at i is some subsequence ending at an earlier j, extended by nums[i] — and that extension is only legal when nums[j] < nums[i].
length[i] = 1 + max( length[j] for every j < i where nums[j] < nums[i] )If no earlier element is smaller, nums[i] starts a fresh subsequence of length 1.
The answer is not length[n-1]
Unlike most DP problems, the final cell is not the answer.
The longest subsequence might end anywhere. In [1, 2, 3, 0] the best ends at index 2, not at the last element. The answer is the maximum over the whole table.
Returning length[n-1] is the most common bug here.
The O(n²) table
nums: 10 9 2 5 3 7 101 18
length: 1 1 1 2 2 3 4 4
↑
5 > 2, so length[3] = 1 + length[2] = 2Every position looks back at everything before it — n positions × n lookbacks = O(n²).
The Faster Idea
O(n²) is acceptable up to about n = 5,000. Beyond that a different angle is needed, and it is genuinely clever.
The second insight
Keep an array tails, where tails[k] holds the smallest possible ending value of an increasing subsequence of length k + 1.
A smaller ending is always at least as good: it is easier to extend. So for each length, remember only the best ending seen so far.
tails stays sorted, which means each new number can be placed with binary search instead of a scan.
For each number x:
- If
xis bigger than everything intails, it extends the longest run — append it. - Otherwise, find the first entry
≥ xand overwrite it. That length is now achievable with a smaller ending.
The answer is the length of tails.
`tails` is not the actual subsequence
This trips people up. tails may contain numbers that never appeared together in one valid subsequence.
Its length is always correct. Its contents are not a real answer. If the problem asks you to return the subsequence itself, you need parent pointers alongside it.
Why overwriting is safe
Replacing tails[k] with a smaller value never shortens anything. The old subsequence of that length still exists — you are simply recording a better ending for future extensions.
And a longer run is never lost, because entries after k are untouched.
Approach
Start with an empty tails
Its length will always equal the best subsequence length found so far.
For each number, binary search tails
Find the leftmost position holding a value ≥ x. This is the standard lower-bound search.
Append or overwrite
If the search runs off the end, x is bigger than everything — append it and the answer grows.
Otherwise overwrite that slot with x, keeping tails sorted and improving that length's ending.
Return the length of tails
Not its contents.
Watch it run
Solution
from bisect import bisect_left
def length_of_lis(nums: list[int]) -> int:
"""O(n log n): tails[k] is the smallest tail of an increasing run of length k+1."""
tails: list[int] = []
for x in nums:
# Leftmost slot holding a value >= x.
position = bisect_left(tails, x)
if position == len(tails):
tails.append(x) # x extends the longest run
else:
tails[position] = x # x gives that length a smaller ending
# The LENGTH is the answer; the contents are not a real subsequence.
return len(tails)
def length_of_lis_quadratic(nums: list[int]) -> int:
"""O(n^2): the plain DP. Clearer, and fast enough up to about n = 5000."""
if not nums:
return 0
# length[i] = best increasing subsequence ENDING at i.
length = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[j] < nums[i]: # strict: equal values cannot extend
length[i] = max(length[i], 1 + length[j])
# The best run may end anywhere, so take the max of the whole table.
return max(length)`bisect_left` vs `bisect_right` decides strict vs non-strict
bisect_left finds the first slot >= x, so an equal value gets overwritten — which enforces strictly increasing.
bisect_right would find the first slot > x, letting equal values sit side by side and giving the non-decreasing answer instead.
One function name is the entire difference between the two problems. The same applies to < versus <= in the quadratic version.
Complexity Analysis
Time Complexity
O(n log n)
Space Complexity
O(n)
- Time — one pass over
nnumbers, each doing a binary search over atailsarray of at mostnentries. - Space —
tailsholds at most one entry per achievable length, soO(n).
| Approach | Time | Space | Use when |
|---|---|---|---|
| Quadratic DP | O(n²) | O(n) | n ≤ 5000, or the subsequence itself is required |
| Tails + binary search | O(n log n) | O(n) | Large n, and only the length matters |
Edge Cases
Related Problems
- Binary Search — the lower-bound search used here
- House Robber — a DP where the last cell is the answer, unlike this one
- Coin Change — building answers up from smaller ones
- Dynamic Programming — the four stages