Longest Increasing Subsequence
Find the longest strictly increasing subsequence in O(n log n).
How it works
Longest Increasing Subsequence (LIS) finds the length of the longest subsequence of a given array in which all elements are in strictly increasing order. Unlike substrings or subarrays, subsequence elements need not be contiguous — they only need to preserve relative order.
The O(n²) DP approach tracks dp[i] = the length of the longest IS ending at index i, but patience sorting achieves O(n log n) by maintaining an auxiliary tails array where tails[k] holds the smallest tail element of all IS of length k+1 seen so far. For each new element a binary search locates where to place or replace in tails, keeping the array sorted and compact.
Why tails stays sorted: every replacement preserves the property that tails[i] < tails[i+1], because we only replace tails[pos] with a value strictly smaller than tails[pos+1] (by the lower_bound invariant).
The length of tails at the end equals the LIS length. While tails itself is not necessarily a valid subsequence, it encodes the patience-sort pile structure used in card game analysis and can be extended with parent-pointer tracking to reconstruct an actual subsequence.
Complexity
Visualizer
Where it's used in the real world
Version control diff algorithms
Computing minimal edit scripts between file revisionsHunt-Szymanski and similar diff algorithms reduce the diff problem to an LIS problem on a list of matching line pairs. Finding the LIS of these matches yields the largest common subsequence, which directly maps to the minimal set of insertions and deletions in the diff output.
Stock price analysis
Finding the longest run of non-decreasing closing pricesQuant analysts use LIS variants to identify momentum streaks and trend-following signals in price series without requiring contiguous windows, making it robust to temporary pullbacks that would break a sliding-window approach.
Scheduling theory (Dilworth's theorem)
Decomposing a partial order into the minimum number of chainsBy Dilworth's theorem, the minimum number of decreasing subsequences needed to partition a sequence equals the length of the longest increasing subsequence. Job schedulers use this to compute the minimum number of parallel execution lanes required for a dependency-ordered task graph.
Implementation
function lisLength(arr: number[]): number {
const tails: number[] = [];
for (const v of arr) {
// Binary search: first index where tails[pos] >= v
let lo = 0, hi = tails.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (tails[mid] < v) lo = mid + 1;
else hi = mid;
}
tails[lo] = v; // extend or replace
}
return tails.length; // LIS length
}
// Usage
console.log(lisLength([10, 9, 2, 5, 3, 7, 101, 18])); // 4
console.log(lisLength([0, 1, 0, 3, 2, 3])); // 4