Longest Increasing Subsequence
Length of the longest strictly increasing subsequence (elements keep order, need not be adjacent).
- 1 <= nums.length <= 2500
- -10⁴ <= nums[i] <= 10⁴
Intuition
The longest increasing subsequence is the longest chain of strictly increasing values in order, not necessarily adjacent. Two solutions are worth knowing, and the second is a genuine idea rather than an optimisation.
The quadratic version is the natural DP. Let dp[i] be the length of the best increasing subsequence ending at index i; it is one more than the best dp[j] among earlier, smaller elements. The answer is the maximum over the whole array. This is the version to write first, and it is the base for many follow-up problems.
The O(n log n) version comes from a sharper observation about which subsequences are worth remembering:
- Among all increasing subsequences of a given length, only the one with the smallest tail matters — it is the easiest to extend.
So keep an array tails where tails[k] is the smallest possible tail of an increasing subsequence of length k + 1. That array is automatically sorted, which makes it binary-searchable.
For each new number, find the first tail that is greater than or equal to it. If none exists, the number extends the longest chain and is appended. Otherwise it replaces that tail — same length, but a smaller ending, which can only help future extensions.
One caution worth stating: tails is not an actual longest increasing subsequence. Its length is correct, but its contents can be a mixture that never appeared together in the input. Reconstructing the real subsequence needs a separate parent array.
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
Before reading on: price up what the direct approach costs here, then ask what a single cell should mean, and which earlier cells it needs. Aim for O(n log n) time and O(n) space.
Start with the quadratic DP
dp[i] = 1 + max(dp[j]) over all j < i with nums[j] < nums[i], defaulting to 1. The answer is max(dp), not dp[n-1] — the best chain may end anywhere, and this is the standard slip.
See which subsequences are worth keeping
For a given length, only the subsequence with the smallest tail can matter, since any number extending a larger tail also extends a smaller one. Every other subsequence of that length is dominated and can be forgotten.
Maintain the tails array
tails[k] holds the smallest tail among increasing subsequences of length k + 1. This array is always sorted, which is what makes the binary search valid — a property that follows from the definition rather than being enforced.
Binary search each new number
Use bisect_left to find the first tail greater than or equal to the number. Left rather than right is what enforces strictly increasing — bisect_right would allow equal values and solve the non-decreasing variant instead.
Append or replace
If no tail qualifies, the number extends the longest chain, so append it and the answer grows. Otherwise overwrite that tail — the length is unchanged but the smaller ending makes future extensions easier.
Do not mistake tails for the answer sequence
Its length is correct, but its contents may never have appeared together in the input. Reconstructing an actual subsequence requires tracking predecessor indices alongside the search.
Cost of both versions
The DP is O(n²) time, O(n) space; the patience version is O(n log n) time, O(n) space. Write the quadratic one first in an interview, then offer the improvement — the reasoning behind it is what is being tested.
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.