Longest Increasing Subsequence in O(n log n), Explained

The longest increasing subsequence has two standard solutions, and interviews tend to want both: the quadratic DP as proof you can set up a recurrence, and the O(n log n) version as the follow-up. The second one is usually taught as a trick — "keep a tails array and binary search it" — which is exactly why it is hard to reproduce under pressure.

It is not a trick. It is the same DP, stored sideways. This article builds it from the quadratic version, then checks both against a brute force.

The problem it solves

Given a list of numbers, find the length of the longest subsequence that is strictly increasing. A subsequence keeps the original order but may skip elements. For [10, 9, 2, 5, 3, 7, 101, 18] the answer is 4 — for example 2, 3, 7, 18.

The same shape appears in less obvious clothing: nesting envelopes, stacking boxes, the longest chain of pairs, and the minimum number of deletions to make a list sorted, which is n minus the LIS length.

The intuition

The quadratic DP. Let best[i] be the length of the longest increasing chain that ends at index i. Every element starts at 1, itself. Then look back at every earlier, smaller element j and take best[j] + 1 if it is bigger. The answer is the maximum over the whole table, not the last cell, because the best chain may end anywhere. That is n²/2 comparisons.

The observation that speeds it up. Suppose two chains have the same length, one ending in 7 and the other ending in 5. For the future, the one ending in 5 is at least as good: anything that can extend the 7-chain can extend the 5-chain too. So for each length, you only need to remember one thing — the smallest possible last value of a chain of that length.

Call that list tails: tails[k] is the smallest value that can end an increasing chain of length k + 1.

Two facts make it fast:

1. tails is always sorted. A chain of length 3 contains a chain of length 2 ending on a smaller value, so the smallest end for length 2 is below the smallest end for length 3.
2. A new value x changes at most one entry. Find the first tail that is at least x. If there is none, x extends the longest chain, so append it. Otherwise x ends a chain of that length more cheaply, so overwrite it.

Because tails is sorted, "find the first tail that is at least x" is a binary search. That is the whole speed-up: the inner loop of the DP becomes a log n lookup.

Watch it run

The animation is the quadratic DP on the example list: for each element it finds the earlier, smaller element with the longest chain and writes best[i] underneath. Watch 4 appear at index 6 and again at the last cell; in general the answer is the maximum of the row, not its last entry. The tails version below does the same job while only remembering one number per length.

The code

Both versions, with a trace of tails so you can see it evolve:

from bisect import bisect_left

def lis_quadratic(nums):
    best = [1] * len(nums)              # best[i] = longest chain ending at i
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                best[i] = max(best[i], best[j] + 1)
    return max(best, default=0)

def lis_length(nums, trace=False):
    tails = []                          # tails[k] = smallest end of a chain of length k+1
    for x in nums:
        k = bisect_left(tails, x)       # first tail that x does not beat
        if k == len(tails):
            tails.append(x)             # x extends the longest chain
        else:
            tails[k] = x                # x is a cheaper end for length k+1
        if trace:
            print(x, tails)
    return len(tails)

print(lis_length([10, 9, 2, 5, 3, 7, 101, 18], trace=True))
# 10 [10]
# 9 [9]
# 2 [2]
# 5 [2, 5]
# 3 [2, 3]
# 7 [2, 3, 7]
# 101 [2, 3, 7, 101]
# 18 [2, 3, 7, 18]
# 4

Watch the step for 3: it replaces 5, because a length-2 chain ending in 3 beats one ending in 5. Nothing about the answer changed, but the future got cheaper — which is why 7 can then extend it.

Here tails happens to finish as a real subsequence. It is not one in general. On [3, 4, 1] it ends as [1, 4] — the 1 came after the 4 — while the length, 2, is still right. To recover an actual subsequence, remember which index sits at each tail and give every element a pointer to the tail it extended:

def lis_sequence(nums):
    tails, tail_idx, prev = [], [], [None] * len(nums)
    for i, x in enumerate(nums):
        k = bisect_left(tails, x)
        if k:
            prev[i] = tail_idx[k - 1]   # x sits on top of the chain one shorter
        if k == len(tails):
            tails.append(x); tail_idx.append(i)
        else:
            tails[k], tail_idx[k] = x, i
    out, i = [], tail_idx[-1] if tail_idx else None
    while i is not None:
        out.append(nums[i])
        i = prev[i]
    return out[::-1]

print(lis_sequence([10, 9, 2, 5, 3, 7, 101, 18]))   # [2, 3, 7, 18]
print(lis_length([3, 4, 1], trace=True))
# 3 [3]
# 4 [3, 4]
# 1 [1, 4]
# 2
print(lis_sequence([3, 4, 1]))                       # [3, 4]

Finally, all three against a brute force that tries every subsequence, longest first. The check also confirms that the rebuilt sequence is strictly increasing and really is a subsequence of the input:

import random
from itertools import combinations

def brute(nums):                        # every subsequence, longest increasing one
    for r in range(len(nums), 0, -1):
        for idx in combinations(range(len(nums)), r):
            if all(nums[a] < nums[b] for a, b in zip(idx, idx[1:])):
                return r
    return 0

def is_subsequence(seq, nums):
    it = iter(nums)
    return all(any(v == x for x in it) for v in seq)

random.seed(11)
ok = True
for _ in range(3000):
    nums = [random.randint(0, 9) for _ in range(random.randint(0, 10))]
    n = brute(nums)
    seq = lis_sequence(nums)
    ok &= lis_length(nums) == lis_quadratic(nums) == n == len(seq)
    ok &= all(a < b for a, b in zip(seq, seq[1:])) and is_subsequence(seq, nums)
print(ok)                                            # True

Three thousand random lists with plenty of duplicates, empty lists included, all agreeing.

The complexity

The quadratic DP is O(n²) time and O(n) space. The tails version does one binary search per element over a list of at most n entries: O(n log n) time, O(n) space including the reconstruction pointers. At n = 100,000 that is the difference between about five billion comparisons and under two million.

Where it goes wrong

• Returning tails as the answer. Its length is right; its contents are not a subsequence in general, as [3, 4, 1] shows.
• The wrong bisect. bisect_left gives strictly increasing. For non-decreasing, use bisect_right: on [7, 7, 7] the first gives 1, the second 3. Mixing them up is silent — both return plausible numbers.
• best[-1] in the quadratic version. The longest chain need not end at the last element.
• Two-dimensional variants. For envelopes, sort by width ascending and height descending for equal widths, then run LIS on heights; the descending tie-break stops two envelopes of the same width from nesting.

The bisect_left versus bisect_right choice is the first-occurrence versus insertion-point distinction from binary search variants.

How to say it in an interview

"The DP is: best chain ending at i is one plus the best over earlier smaller elements, O(n²). To speed it up, notice that among chains of the same length, only the smallest ending value matters. I keep those in a tails array, which stays sorted, so each new element is one binary search — either it extends the longest chain or it lowers one tail. That's O(n log n). The array's length is the answer; its contents aren't the subsequence, so if you need that I'll keep parent pointers."

Saying why tails is sorted is the part that turns a memorised trick into an argument.