DPAlgorithmaka LIS, patience sorting

Longest Increasing Subsequence

Find the length of the longest strictly increasing subsequence — O(n²) DP or O(n log n) with patience sorting.

▶ VisualizePattern: Binary SearchPractice (1)
Progress

Overview

A subsequence keeps relative order but may skip elements. Given nums, the LIS is the longest subsequence whose elements strictly increase. For [10, 9, 2, 5, 3, 7, 101, 18] the answer is 4 (2, 3, 7, 101 or 2, 5, 7, 18).

Two standard algorithms: an O(n²) DP where dp[i] is the LIS ending at i, and an O(n log n) method that maintains the smallest possible tail of an increasing subsequence for each length and updates it by binary search. The second is what to reach for when n is 10^5.

1D DPsubsequencebinary searchpatience sortingO(n log n)

Intuition

A mental model before the formal terms.

Take [3, 1, 4, 1, 5]. Ask each element: "what is the longest increasing run that *ends on you*?" For 3: 1. For 1: 1 (nothing smaller before it). For 4: it can extend the run ending at 3 or at 1 → 2. For the second 1: 1. For 5: it can extend any of the runs ending at 3, 1, 4, 1; the longest is at 4 (length 2) → 3. The answer is the maximum over all elements.

For the fast version, imagine dealing the cards [3, 1, 4, 1, 5] into piles, each new card going onto the leftmost pile whose top is ≥ it, or starting a new pile on the right. Piles: 3 → [3]; 1 → [1] (replaces 3); 4 → [1][4]; 1 → [1][4]; 5 → [1][4][5]. The number of piles, 3, is the LIS length. The pile tops are always increasing, and each top is the smallest value that can end a subsequence of that length.

How it works

  1. State (quadratic): dp[i] = length of the longest strictly increasing subsequence that ends exactly at index i.
  2. Transition: dp[i] = 1 + max(dp[j]) over all j < i with nums[j] < nums[i]; if there is no such j, dp[i] = 1.
  3. Base case: every dp[i] starts at 1 (the element alone).
  4. Iteration order: i from left to right; inner j over 0..i-1.
  5. Answer location: max(dp) — not dp[n-1], because the LIS need not end at the last element.
  6. Space optimization: none for the quadratic form (needs all previous dp[j]). The O(n log n) variant replaces dp with an array tails where tails[k] = smallest tail of any increasing subsequence of length k+1. For each x, binary search the first tails[k] ≥ x (lower bound) and set tails[k] = x, or append if none. len(tails) is the answer. Note tails is not the LIS itself; to reconstruct the subsequence keep a parent pointer per element.

Why it works

Optimal substructure: if nums[i] is the last element of an optimal subsequence, then the elements before it form an increasing subsequence ending at some j < i with nums[j] < nums[i], and it must be the longest such — otherwise we could substitute a longer one. So dp[i] computed from the best valid dp[j] is exact.

For the patience method the invariant is: after processing a prefix, tails is strictly increasing and tails[k] is the minimum possible last element among increasing subsequences of length k+1 in that prefix. Placing x at the lower-bound position preserves both: x extends the length-k subsequence ending at tails[k-1] < x, and replacing tails[k] with the smaller x can only make future extensions easier. Since tails is increasing, binary search is valid.

The number of entries in tails equals the LIS length because an entry at index k exists only after a genuine increasing subsequence of length k+1 was found, and every such subsequence causes an entry to exist.

Recognition

How to tell a problem wants this.

  • "Longest increasing/decreasing subsequence", "longest chain", "maximum number of nested boxes/envelopes".
  • The input is a sequence and elements may be skipped but not reordered.
  • n ≤ 2500 allows O(n²); n ≤ 10^5 demands O(n log n).
“sorted array” → Binary Search“number of ways” → Dynamic Programming

Interactive visualization

Play, step, change the input. ← → and space work too.

3
0
1
1
8
2
2
3
5
4
4
5
9
6
6
7
01234567
11111111
1/30dp[i] = length of the longest increasing subsequence ending exactly at i. Every element alone is a subsequence of length 1.
Cell being filledDependency readBase caseComputedReconstructed choice
PseudocodeLearn Longest Increasing Subsequence →
1dp[i] = 1 for all i   // LIS ending at i
2for i in 1 .. n-1:
3  for j in 0 .. i-1:
4    if a[j] < a[i] and dp[j] + 1 > dp[i]:
5      dp[i] = dp[j] + 1; prev[i] = j
6answer = max(dp); reconstruct via prev
Variables
n8
Complexity
best O(n log n)
avg O(n log n)
worst O(n log n)
space O(n)
Speed

Pseudocode

1tails = []
2for x in nums:
3  k = lower_bound(tails, x)   # first index with tails[k] >= x
4  if k == len(tails): tails.append(x)
5  else: tails[k] = x
6return len(tails)

Implementations

1from bisect import bisect_left
2 
3 
4# Patience sorting: tails[k] = smallest tail of a strictly increasing
5# subsequence of length k + 1. tails is always sorted.
6def length_of_lis(nums: list[int]) -> int:
71 · Tails array
8    tails: list[int] = []
9    for x in nums:
102 · Lower bound search
11        k = bisect_left(tails, x)  # bisect_right for non-decreasing
123 · Extend or replace
13        if k == len(tails):
14            tails.append(x)
15        else:
16            tails[k] = x
174 · Answer
18    return len(tails)
Walkthrough
  1. bisect_left(tails, x) returns the first index with tails[k] >= x — exactly the lower bound the algorithm needs.
  2. Appending grows the LIS by one; assignment records a smaller tail for an existing length, keeping future options open.
  3. tails stays sorted by induction: we only ever overwrite with a value smaller than the old one but larger than its left neighbour.
  4. The function is O(n log n) end to end because bisect_left is C-implemented binary search.
Complexity (this implementation)
time O(n log n) · space O(n)

bisect operates on the list in place; no slicing, so no hidden O(n) copies.

Language notes
  • Use bisect_right instead of bisect_left for a non-decreasing subsequence (duplicates allowed).
  • bisect accepts key= from Python 3.10, useful when the LIS runs over tuples or objects.
  • The memoized O(n²) recursion can hit the default 1000-frame recursion limit on long inputs — prefer the iterative table or this patience version.
Common mistakes in this language
  • Using bisect_right for a strictly increasing LIS — duplicate values then chain.
  • Returning tails as if it were the subsequence; only len(tails) is meaningful.
  • Rebuilding tails with sorted() each step "to be safe" — O(n² log n) and unnecessary.
Language differences that matter here
  • Binary search comes from the stdlib in C++ (std::lower_bound) and Python (bisect_left); JS/TS must hand-roll it — indexOf/findIndex are linear and destroy the log factor.
  • Strict vs non-decreasing is the same switch everywhere: lower bound (bisect_left) for strict, upper bound (bisect_right) to allow duplicates.
  • Recursive O(n²) variants risk Python's 1000-frame recursion limit and JS engine stack limits on long inputs; the iterative forms are safe in all four languages.

Complexity

Best
O(n log n)
Average
O(n log n)
Worst
O(n log n)
Space
O(n)

The classic DP is O(n²) time, O(n) space. Patience sorting is O(n log n); reconstruction needs an extra O(n) parent array.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Longest increasing/decreasing/non-decreasing subsequence, or the count of such subsequences (quadratic DP with a count array).
  • Chains of objects ordered by one key and searched by another: Russian doll envelopes (sort by width, LIS on height with a tie-breaking trick), box stacking, maximum length of pair chain.
  • Minimum deletions to make a sequence sorted = n - LIS.
Avoid it when
  • Contiguous increasing runs ("longest increasing subarray") — a single linear scan suffices.
  • When you need *all* LIS or their count with n ≥ 10^5 — needs a Fenwick tree keyed by value, not plain patience.
  • Two-sequence problems (common subsequence) — that is Longest Common Subsequence, a 2D table.

Alternatives

Longest Common SubsequenceBinary SearchFenwick TreeSubsequence DP

Common mistakes

  • Returning dp[n-1] instead of max(dp) in the quadratic version.
  • Reading tails as the actual LIS — its contents are not a valid subsequence in general, only its length is meaningful.
  • Using bisect_right / upper bound for a *strictly* increasing LIS (allows duplicates) or bisect_left for non-decreasing (forbids them).
  • In Russian Doll Envelopes, forgetting to sort heights in descending order for equal widths, which lets equal-width envelopes chain.

Interview patterns

  • Longest Increasing Subsequence (length) and Number of LIS (count array alongside dp).
  • Russian Doll Envelopes: sort by width asc, height desc; LIS on heights.
  • Longest Bitonic Subsequence: LIS from the left plus LIS from the right, minus 1.
  • Minimum number of removals to make an array sorted, or minimum patience-sort piles.
Interview questions on this
Mock interviews

Example problems

Longest Increasing Subsequencemedium