Longest Increasing Subsequence

What the LIS problem asks

Given an array of numbers such as [10, 9, 2, 5, 3, 7, 101, 18], the longest increasing subsequence is [2, 3, 7, 18] (or equivalently [2, 3, 7, 101]) with length 4. A subsequence preserves the original left-to-right order but is allowed to skip elements — so the members of the LIS live at non-adjacent indices. That is the single most common point of confusion: LIS is not the longest increasing subarray (a contiguous run), which is trivial to find in O(n).

Formally: find indices i₁ < i₂ < … < i_k such that a[i₁] < a[i₂] < … < a[i_k] and k is maximized. "Strictly increasing" is the default; a "non-decreasing" variant allows equal consecutive values and needs only a one-line change (see below).

Why LIS matters

• Diff and patch reconciliation. The patience-diff algorithm in git diff --patience and Bazaar matches unchanged lines by finding a longest increasing subsequence of the positions of lines that appear exactly once in both files, so the "moved but unchanged" lines are aligned into a cleaner diff.
• Scheduling and stacking. Classic problems — maximum number of non-overlapping airplane landings by (arrival, departure), the tallest stack of nested boxes, Russian-doll envelopes — reduce to LIS after a sort.
• The Erdős–Szekeres theorem. Any sequence of more than (r-1)(s-1) distinct reals contains an increasing subsequence of length r or a decreasing one of length s. LIS is the constructive side of this pigeonhole classic.
• Interview signal. LIS is a compact test of whether a candidate can spot that an O(n²) DP hides an O(n log n) structure via binary search — the same leap that separates naive from optimal in dozens of problems.

The O(n²) dynamic programming approach

Let dp[i] be the length of the longest increasing subsequence that ends at index i. Every single element is an LIS of length 1, so initialize all dp[i] = 1. Then for each i, look back at every j < i: if a[j] < a[i], the subsequence ending at j can be extended by i, so dp[i] = max(dp[i], dp[j] + 1). The answer is max(dp). Two nested loops give O(n²) time and O(n) space.

This is a clean illustration of optimal substructure: the best subsequence ending at i is built from the best subsequence ending at some earlier compatible j. The bottleneck is the inner scan for the best predecessor — which is exactly what binary search replaces.

The O(n log n) method: patience sorting + binary search

Imagine dealing the array as playing cards, one at a time, into piles — the solitaire game patience. The rule: place each card on the leftmost pile whose top card is ≥ the new card (for a strictly increasing LIS); if no such pile exists, start a new pile to the right. Because the top cards of the piles are always in sorted order, "leftmost pile with top ≥ x" is precisely a lower_bound binary search. The number of piles at the end equals the LIS length — a beautiful theorem due to the patience-sorting analysis popularized by Aldous and Diaconis (1999).

In code we don't store whole piles; we keep one array tails, where tails[len] holds the smallest possible tail value of any increasing subsequence of length len+1 seen so far. For each new value x: binary-search for the first tail ≥ x and overwrite it with x (keeping tails as small as possible so future elements have the best chance to extend); if x exceeds every tail, append it (the LIS grew by one). The final tails.length is the answer. Each of the n elements does one O(log n) binary search — O(n log n) total.

Key subtlety: the tails array is not itself a valid LIS — it can mix values from incompatible subsequences. It only tracks the best achievable tail per length. To recover the actual sequence you need parent pointers, covered below.

DP vs patience-sorting comparison

	Naive DP	Patience + binary search	Longest increasing subarray
Time	O(n²)	O(n log n)	O(n)
Space	O(n)	O(n)	O(1)
Contiguous?	No (subsequence)	No (subsequence)	Yes (subarray)
Reconstruction	Trivial (back-pointer to argmax dp[j])	Parent-pointer array required	Track start/end indices
Handles n = 10⁶?	Too slow (~10¹²)	Yes (~2×10⁷)	Yes
Core trick	Best predecessor scan	lower_bound replaces the scan	Reset run on a decrease

Reconstructing the subsequence

Because the O(n log n) method only manipulates tail values, we augment it with two arrays. pileIndex[k] records the array index of the element currently sitting on pile k. parent[i] records, for the element at index i, the index that was on the pile immediately to its left when i was placed — that is its predecessor in an optimal subsequence. After the pass, start from the index on the highest pile and follow parent pointers back to the beginning, then reverse. The result is a genuine longest increasing subsequence, and the extra work is O(n) time and space.

How it works in Python

from bisect import bisect_left

def lis_length(a):
    """O(n log n) length of the strictly increasing LIS."""
    tails = []                      # tails[k] = smallest tail of an LIS of length k+1
    for x in a:
        i = bisect_left(tails, x)   # first tail >= x  (lower_bound)
        if i == len(tails):
            tails.append(x)         # x extends the longest subsequence
        else:
            tails[i] = x            # x is a better (smaller) tail for that length
    return len(tails)

def lis_reconstruct(a):
    """O(n log n) length AND one actual longest increasing subsequence."""
    n = len(a)
    tails = []          # tail VALUES per pile
    pile_idx = []       # array index sitting on each pile
    parent = [-1] * n   # predecessor index in the subsequence
    for i, x in enumerate(a):
        p = bisect_left(tails, x)
        if p == len(tails):
            tails.append(x)
            pile_idx.append(i)
        else:
            tails[p] = x
            pile_idx[p] = i
        parent[i] = pile_idx[p - 1] if p > 0 else -1
    # walk parent pointers back from the top pile
    seq, k = [], pile_idx[-1]
    while k != -1:
        seq.append(a[k])
        k = parent[k]
    seq.reverse()
    return len(tails), seq

print(lis_reconstruct([10, 9, 2, 5, 3, 7, 101, 18]))
# (4, [2, 3, 7, 18])

For a non-decreasing LIS (equal consecutive values allowed), change bisect_left to bisect_right (upper_bound). Everything else — piles, parent pointers, complexity — is identical.

Worked example: tracing the piles

Deal [10, 9, 2, 5, 3, 7, 101, 18]:

• 10 → tails = [10]
• 9 → replaces 10 → tails = [9]
• 2 → replaces 9 → tails = [2]
• 5 → bigger than all → append → tails = [2, 5]
• 3 → replaces 5 → tails = [2, 3]
• 7 → append → tails = [2, 3, 7]
• 101 → append → tails = [2, 3, 7, 101]
• 18 → replaces 101 → tails = [2, 3, 7, 18]

Final length = 4. Notice the last replacement: 18 overwrites 101 so that a future element between 18 and the next larger value could still extend the length-4 subsequence. The parent-pointer walk recovers [2, 3, 7, 18]. Note that tails happened to be a valid LIS here only by luck — in general it is not.

Common misconceptions and pitfalls

• Confusing subsequence with subarray. LIS skips elements; the longest increasing run must be contiguous. Different problem, different answer.
• Treating tails as the answer sequence. It stores best tails per length, not a coherent subsequence. Always reconstruct with parent pointers.
• Wrong bisect for the wrong variant. bisect_left gives strictly increasing; bisect_right gives non-decreasing. Swapping them silently changes the definition.
• Assuming the LIS is unique. The length is unique; the sequence usually is not. [1, 3, 2, 4] has both [1, 3, 4] and [1, 2, 4].
• Reaching for LIS when a subarray suffices. If the problem truly wants contiguity, LIS is overkill and gives a wrong (longer) answer.
• Off-by-one on the empty array. An empty input has LIS length 0; a single element has length 1. The tails formulation handles both without special cases.

Notable variants and reductions

• Longest decreasing subsequence. Negate the values (or reverse the comparison) and run LIS.
• Russian Doll Envelopes (LeetCode 354). Sort by width ascending, height descending for equal widths, then LIS on heights — the descending tie-break prevents same-width envelopes from chaining.
• Number of LIS (LeetCode 673). Augment the DP with a count[i] tracking how many longest subsequences end at i; the O(n log n) count variant uses a Fenwick/segment tree keyed by value.
• Bitonic and cross-cutting problems. Longest bitonic subsequence combines a forward LIS with a backward LIS at each index.