Longest increasing subsequence
mediumdp[i] means 'ending exactly at i' - anchoring the subproblem is what makes the recurrence work. Then switch to patience sorting and watch binary search remove the inner loop.
O(n log n) patienceWorst O(n²) DPSpace O(n)Saved in this browser - no sign-up, nothing sent anywhere.
How longest increasing subsequence works
dp[i] is the length of the longest increasing subsequence that ends exactly at index i. The anchor matters: knowing the last element means any earlier index j with a[j] < a[i] can be extended by a[i], so dp[i] is the best dp[j] + 1, starting from 1. Because the subsequence can end anywhere, the final answer is the maximum over the whole array - not dp[n-1].
Two nested loops give the O(n²) table - 28 pairwise comparisons for 8 elements, against the 2^8 = 256 subsequences brute force would test, and the gap explodes from there. The quadratic version's payoff is a real traceback: a prev array remembers which index each dp value extended, so the subsequence itself can be rebuilt, not just measured.
The O(n log n) patience version keeps a different structure: tails[k] holds the smallest value that can end an increasing run of length k + 1. Each new element either extends the longest run or replaces the first tail at least as large - found by binary search, because tails stays sorted. A smaller tail is never worse: it can only be extended more often.
Step by step
- Take 10, 9, 2, 5, 3, 7, 101, 18. Every dp entry starts at 1 - each element alone is a valid subsequence.
- 10, 9 and 2 extend nothing - no earlier value is smaller than any of them - so their dp stays 1.
- 5 sees the 2 before it and records dp = 2. 3 also extends only the 2, so it records 2 as well.
- 7 scans left: extending the run ending at 5 gives dp = 3. The runs 2, 5, 7 and 2, 3, 7 tie at length 3.
- 101 extends the length-3 run ending at 7 and reaches 4. 18 does the same - two different length-4 endings.
- The best dp value is 4. Following prev pointers back from 101 - through 7, 5, 2 - rebuilds the subsequence 2, 5, 7, 101.
Complexity
| Best case time | O(n log n) patience |
|---|---|
| Worst case time | O(n²) DP |
| Space | O(n) |
tails[] stays sorted, so the update position is found by binary search.
Reference implementation
Python
def lis_quadratic(a):
n = len(a)
dp = [1] * n
for i in range(n):
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp, default=0)
from bisect import bisect_left
def lis_fast(a):
"""O(n log n). tails[k] = smallest possible tail of an
increasing subsequence of length k+1."""
tails = []
for x in a:
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x) # extends the longest run
else:
tails[i] = x # a smaller tail is strictly better
return len(tails) # NOTE: tails is not the subsequenceJavaScript
function lisFast(a) {
const tails = [];
for (const x of a) {
let lo = 0, hi = tails.length;
while (lo < hi) { // lower bound
const mid = (lo + hi) >> 1;
if (tails[mid] < x) lo = mid + 1; else hi = mid;
}
tails[lo] = x; // append or replace
}
return tails.length;
}Worth noticing
dp[i] means 'ending exactly at i'
Anchoring the subproblem to a specific last element is what makes the recurrence work: extend any earlier subsequence whose last value is smaller. The answer is the maximum over all i, not dp[n−1].
The patience version stores tails, not the answer
tails[k] is the smallest value that can end an increasing subsequence of length k+1. Its *length* is the answer, but its contents are usually not a valid subsequence of the input - a trap worth knowing.
Why replacing a tail is always safe
A smaller tail can only be extended more often. Swapping it in never shortens what is already achievable, and may allow a longer run later - so the greedy replacement never loses.
Binary search is what removes the inner loop
tails is sorted by construction, so the position to update is found in O(log n) instead of by scanning. That single observation takes the algorithm from quadratic to linearithmic.
Common pitfalls
- Returning dp[n-1] instead of the maximum over all of dp. The longest run rarely ends at the final element - here it ends at 101, two positions early.
- Using <= instead of < when testing a[j] against a[i]. Equal values then chain, and the result quietly becomes longest non-decreasing subsequence.
- Reading tails[] as the answer. Its length is the LIS length, but its contents are generally not a subsequence of the input at all.
- Using an upper-bound search in the patience version. Equal elements then land past their twin instead of replacing it - the same non-decreasing bug by another route.
- Expecting the patience version to produce the subsequence. Without extra parent bookkeeping it yields only the length - the quadratic table is what powers the traceback.
Where it is used
- Russian doll envelopes and box stacking - sort one dimension, run LIS on the other.
- Patience solitaire, the card game the fast method is named for - the pile count equals the LIS length.
- Finding the longest improving trend in time-series data - sales, benchmarks, sensor readings.
- LeetCode 300, and the reason lower-bound binary search is worth knowing cold in interviews.
Frequently asked questions
What is the time and space complexity of longest increasing subsequence?
The table version costs O(n²) - two nested loops - and the patience version O(n log n), one binary search per element. Both need O(n) space. At n = 1,000 that is roughly 500,000 pairwise comparisons against about 10,000 binary-search steps, which is why the patience form matters.
Why is it called patience sorting?
It mirrors the card game patience: deal values onto piles, placing each card on the leftmost pile whose top is not smaller, starting a new pile otherwise. The number of piles equals the LIS length, and tails[] stores exactly the pile tops.
Is tails[] the actual longest increasing subsequence?
No. tails[k] is the smallest value that can end an increasing run of length k + 1, and replacements overwrite history - the final contents are usually not a subsequence of the input in order. Only the length is meaningful; recovering the sequence needs parent pointers or the O(n²) table.
How do I find the longest non-decreasing subsequence instead?
Relax the strictness. In the table version test a[j] <= a[i] instead of a[j] < a[i]; in the patience version switch the lower-bound search for an upper bound, so equal values extend runs rather than replace tails.