Algorithms from zero
Longest increasing subsequence: O(n^2) DP and the O(n log n) tails trick
You have an array of numbers and want the length of the longest run that keeps going up—but the numbers do not have to sit next to each other. From [10, 9, 2, 5, 3, 7, 101, 18] you can pick 2, 5, 7, 101 (or 2, 3, 7, 18): four numbers, each bigger than the last, scattered across the array. That is a subsequence, not a contiguous slice. This is the longest increasing subsequence (LIS) problem. The natural one-dimensional DP solves it in O(n^2). Then a clever trick—keep a tiny array of “best tails” and binary-search it—drops the cost to O(n log n). The twist that trips everyone up: that tails array gives the right length, but it is not itself a valid subsequence.
After this lesson you can define LIS precisely: the longest strictly-increasing subsequence of an array, where elements keep their relative order but need not be adjacent. You can write the O(n^2) DP—dp[i] is the length of the longest increasing subsequence that ends at index i, computed as 1 + max(dp[j]) over all j < i with nums[j] < nums[i], and the answer is max(dp). You can write the O(n log n) method: maintain a tails array where tails[k] is the smallest possible last value of an increasing subsequence of length k+1, and for each new value binary-search the first tail that is >= x and overwrite it (or append). You understand exactly why tails.length is the LIS length while tails itself is not a real subsequence. You can state both complexities. Next lesson continues the DP-on-sequences arc.
What is the longest increasing subsequence?
A subsequence is what you get by deleting zero or more elements from an array without reordering the rest. So [2, 7, 18] is a subsequence of [10, 9, 2, 5, 3, 7, 101, 18], but [7, 2] is not (wrong order). The longest increasing subsequence (LIS) is the longest such subsequence whose values are strictly increasing (each element strictly greater than the previous).
nums = [10, 9, 2, 5, 3, 7, 101, 18]
one LIS = 2, 5, 7, 101 (length 4)
another = 2, 3, 7, 18 (length 4)There can be several LIS of the same length; we usually only want the length. Note “subsequence” (scattered, order kept) is different from “subarray/substring” (contiguous). LIS does not require the picked elements to be neighbors.
Approach 1: the O(n^2) one-dimensional DP
Define the state dp[i] = the length of the longest increasing subsequence that ends exactly at index i. Every increasing subsequence ends somewhere, so the answer is max(dp) over all i.
How do we fill dp[i]? A subsequence ending at i is some shorter subsequence ending at an earlier index j < i with nums[j] < nums[i], plus nums[i] tacked on. To make it as long as possible, pick the best such j:
dp[i] = 1 + max( dp[j] ) over all j < i with nums[j] < nums[i]
dp[i] = 1 if no such j exists (nums[i] starts fresh)
answer = max(dp[0..n-1])Every element alone is a subsequence of length 1, so we initialize every dp[i] = 1. Two nested loops (i outer, j inner) give O(n^2).
Approach 2: the O(n log n) tails array
The O(n^2) DP re-scans all earlier indices for every i. The faster method replaces that scan with a binary search by maintaining one small array, tails:
tails[k]= the smallest possible last value of any increasing subsequence of lengthk + 1.
Why “smallest possible”? Because a smaller tail is easier to extend later—it leaves more room for a future element to be larger than it. Keeping the minimum tail per length is greedy in exactly the right way. The length of tails at the end is the LIS length.
For each value x in nums, do one of two things:
- Append: if
xis larger than every tail (larger thantails[last]), it extends the longest run by one, so push it. - Replace: otherwise, find the first tail that is
>= xand overwrite it withx. This says “a subsequence of that length can now end in a smaller valuex,” which can only help future extensions. Finding that position is a binary search (a lower bound: the first index wheretails[idx] >= x), becausetailsis always sorted in increasing order.
This is the patience-sorting idea (deal cards onto piles, each pile sorted; the number of piles is the LIS length).
Watch tails evolve
Walk nums = [10, 9, 2, 5, 3, 7, 101, 18] through the tails rule. Each step either appends (new longest length found) or replaces the first tail >= x:
x = 10 append tails = [10]
x = 9 replace tails[0] tails = [9]
x = 2 replace tails[0] tails = [2]
x = 5 append tails = [2, 5]
x = 3 replace tails[1] tails = [2, 3]
x = 7 append tails = [2, 3, 7]
x = 101 append tails = [2, 3, 7, 101]
x = 18 replace tails[3] tails = [2, 3, 7, 18]Final tails = [2, 3, 7, 18], length 4. The LIS length is 4. (Here the final tails happens to be a real subsequence, but that is luck—see the Inset on why it is not guaranteed.)
Why is tails always sorted? Length-k subsequences can end in a value at least as small as length-(k-1) ones plus one more step up, so longer runs need larger minimum tails. The invariant “tails strictly increasing” holds throughout, which is exactly what lets us binary-search it.
The O(n^2) DP (clear and direct)
State dp[i] = length of the longest increasing subsequence ending at i.
1
function lisN2(nums) {
2
if (nums.length === 0) return 0;
3
// dp[i] = length of LIS ending exactly at index i. Every element alone is length 1.
4
const dp = new Array(nums.length).fill(1);
5
6
for (let i = 1; i < nums.length; i++) {
7
for (let j = 0; j < i; j++) {
8
// Can we extend the subsequence ending at j by appending nums[i]?
9
if (nums[j] < nums[i]) {
10
dp[i] = Math.max(dp[i], dp[j] + 1);
11
}
12
}
13
}
14
// The LIS can end at any index, so take the best dp value.
15
return Math.max(...dp);
16
}
- L2 Empty input has no subsequence: length 0.
- L4 Initialize every dp[i] to 1 - a single element is an increasing subsequence of length 1.
- L6 Outer loop: compute dp[i] for each position in turn.
- L7 Inner loop: scan all earlier indices j as candidate predecessors.
- L9 Only a strictly smaller earlier value can sit before nums[i] in an increasing run.
- L10 Take the best predecessor: dp[i] = 1 + max(dp[j]) over valid j.
- L15 The answer is the maximum dp[i] - the LIS may end anywhere.
The O(n log n) tails method
Maintain tails, where tails[k] is the smallest tail of any increasing subsequence of length k+1. For each x, binary-search the first tail >= x (lower bound). Append if none exists, otherwise overwrite that tail.
1
function lengthOfLIS(nums) {
2
const tails = [];
3
4
for (const x of nums) {
5
// Binary search: find the first index where tails[idx] >= x (lower bound).
6
let lo = 0, hi = tails.length;
7
while (lo < hi) {
8
const mid = lo + Math.floor((hi - lo) / 2);
9
if (tails[mid] < x) {
10
lo = mid + 1; // tails[mid] too small - x belongs to the right
11
} else {
12
hi = mid; // tails[mid] >= x - candidate, but keep looking left
13
}
14
}
15
16
if (lo === tails.length) {
17
tails.push(x); // x beats every tail: a new longest length
18
} else {
19
tails[lo] = x; // overwrite the first tail >= x with the smaller x
20
}
21
}
22
23
return tails.length; // LENGTH is the LIS length (tails itself is NOT a subsequence)
24
}
- L2 tails grows to the LIS length; tails[k] is the smallest possible last value of a length-(k+1) run.
- L6 Lower-bound binary search over the sorted tails array - this is the O(log n) step.
- L9 tails[mid] < x means x must go further right: move lo past mid.
- L11 tails[mid] >= x is a candidate replacement spot: shrink hi to mid, never below the answer.
- L16 lo == tails.length means no tail was >= x, so x extends the longest run: append it.
- L19 Otherwise overwrite tails[lo] with x: same length, but now a smaller tail (easier to extend).
- L23 Return the length only. The contents of tails are not guaranteed to be a real subsequence.
Run both and compare
Both methods must agree on the length. The tails method does it in O(n log n).
The all-equal array [7, 7, 7, 7, 7] returns 1: “strictly increasing” rejects equal neighbors, so each 7 just keeps replacing tails[0] and the length never grows past 1.
Watch the tails array fill for nums = [10, 9, 2, 5, 3, 7, 101, 18]. Each step is one value x: either an append (a longer run is now possible) or a replace (the first tail >= x, found by binary search, becomes the smaller x). The cells show the current tails.
1
for (const x of nums) {
2
// lower bound: first idx with tails[idx] >= x
3
if (lo === tails.length) tails.push(x); // append
4
else tails[lo] = x; // replace
5
}
| Method | Time | Space |
|---|---|---|
| O(n^2) DP | O(n^2) — two nested loops over the array | O(n) — the dp array |
| Tails + binary search | O(n log n) — n values, each a O(log n) search | O(n) — the tails array |
Why the DP is O(n^2)
The outer loop runs n times; for each i the inner loop scans up to i earlier indices. That is 1 + 2 + ... + (n-1) ≈ n^2 / 2 comparisons = O(n^2). Space is the single dp array of length n = O(n).
Why the tails method is O(n log n)
Each of the n values triggers exactly one binary search over tails, and tails never exceeds length n, so each search is O(log n). The append/replace is O(1). Total: n × O(log n) = O(n log n). Space is the tails array, at most n entries = O(n).
time space
O(n^2) DP O(n^2) O(n)
tails + bsearch O(n log n) O(n) <- this lesson's speedupWhen does the speedup matter? For n = 100,000, n^2 is ten billion operations; n log n is about 1.7 million. The tails method is the standard answer when n is large. The O(n^2) DP is easier to reason about and is the one to write first if you also need to reconstruct the actual subsequence (the tails method needs extra bookkeeping for that).
What is the length of the LIS of [3, 1, 8, 2, 5]?
In the O(n^2) DP, what does dp[i] represent?
In the tails array, what is tails[k]?
For each value x, the tails method binary-searches for which position?
Why is `tails.length` the LIS length, even though `tails` is not necessarily a real subsequence?
What is the LIS length of the strictly-increasing array [1, 2, 3, 4, 5]?
Common mistake
The tails array is NOT the actual subsequence. Its length is the LIS length, but its contents can be values that never appeared together in one increasing run. Concrete proof: nums = [2, 5, 3, 7, 11, 8, 10, 13, 6] ends with final tails = [2, 3, 6, 8, 10, 13] (length 6, which is the correct LIS length). But [2, 3, 6, 8, 10, 13] is not a subsequence of nums: the 6 is the very last element of nums, yet here it sits in the middle of tails ahead of 8, 10, 13. The last replacement (6 overwriting 7) lowered a tail for a length that was already finalized, corrupting the contents while leaving the length correct. To recover the real subsequence you must store predecessor links separately; the tails array alone only gives you the length.
Why this works
Why keep the smallest tail per length? Greedy intuition: if two increasing subsequences both have length k, the one ending in the smaller value is strictly more useful, because any future element that can extend the larger-tailed one can also extend the smaller-tailed one (and possibly more). So we never lose anything by always remembering the minimum tail for each length. That is the invariant the tails array maintains, and it is why overwriting the first tail >= x with the smaller x is always safe.
Edge cases
Strictly increasing vs. non-decreasing. This lesson computes the strictly increasing LIS, so equal neighbors do not count: [7, 7, 7] has LIS length 1. If instead you want the longest non-decreasing subsequence (allowing equal values), change the binary search from lower bound (first tail >= x) to upper bound (first tail > x). That one-line change flips strict to non-strict. Mixing them up is the most common LIS bug: always confirm which the problem wants.
More practice
Recipe to apply. (1) State the variant: strictly increasing or non-decreasing? (2) For a first correct solution or when you must reconstruct the actual subsequence, write the O(n^2) DP: dp[i] = 1 + max(dp[j]) over j < i with nums[j] < nums[i], answer max(dp). (3) For large n, switch to the tails method: for each x, lower-bound binary search, then append or replace, and return tails.length. (4) Remember the caveat: the tails array’s length is the answer, but its contents are not a guaranteed subsequence.
Explain the LIS problem, the O(n^2) DP, the O(n log n) tails method, and why tails.length is the answer even though tails is not a real subsequence.
The longest increasing subsequence (LIS) is the longest strictly-increasing subsequence of an array—elements keep their order but need not be contiguous.
O(n^2) DP: dp[i] = length of the LIS ending at index i = 1 + max(dp[j]) over all j < i with nums[j] < nums[i]; initialize each dp[i] = 1; the answer is max(dp). Time O(n^2), space O(n).
O(n log n) tails method: keep tails where tails[k] is the smallest last value of any increasing subsequence of length k+1. For each x, binary-search the first tail >= x (a lower bound); append x if every tail is smaller, otherwise overwrite that tail with the smaller x. The answer is tails.length. Time O(n log n), space O(n).
The key caveat: tails.length is the LIS length, but tails itself is not a guaranteed subsequence—its values can come from different runs (proof: [2, 5, 3, 7, 11, 8, 10, 13, 6] ends with tails [2, 3, 6, 8, 10, 13], length 6 correct, contents impossible as one run). To recover the real subsequence, track predecessor links separately.
Strict vs. non-decreasing: lower bound (first tail >= x) gives strictly increasing; switch to upper bound (first tail > x) for the non-decreasing variant.