DSA LIS in O(n log n)

The problem

The Longest Increasing Subsequence problem asks for the length of the longest run of values that keeps rising while keeping its order in the list. A subsequence keeps the order of the list and may skip values. Rising here means strictly rising, so equal values never extend a run.

The answer is a length, not the run itself. The cases below include a falling list, an empty list, and a list of repeats.

cases = [
    ([10, 9, 2, 5, 3, 7, 101, 18], 4),
    ([3, 1, 4, 2, 5], 3),
    ([1, 2, 3, 4], 4),
    ([5, 4, 3, 2, 1], 1),
    ([2, 2, 2], 1),
    ([], 0),
]
for nums, expected in cases:
    print("nums", nums, "longest length:", expected)

The first row hides its best run. The values 2, 3, 7 and 18 rise in order, and no five values in that row do.

Intuition: grab each next larger value

The first idea walks the list once and takes every value larger than the last taken value. The walk is fast. The first value taken decides everything, and a large early value blocks the walk.

def greedy_run(nums):
    run = []
    for x in nums:
        if not run or x > run[-1]:
            run.append(x)
    return run

print("greedy run:", greedy_run([10, 9, 2, 5, 3, 7, 101, 18]), "length:", len(greedy_run([10, 9, 2, 5, 3, 7, 101, 18])))
print("best length for that list is:", 4)

The greedy walk takes 10 first and is stuck with a run of two. A good method must keep cheaper starting points alive at the same time. Keeping one candidate tail per length does exactly that.

Brute force: compare each value with every earlier value

The brute force records, for each position, the longest run ending exactly there. Each record reads every earlier record whose value is smaller. A counter records the comparisons.

def lis_slow(nums):
    best = [1] * len(nums)
    checks = 0
    for i in range(len(nums)):
        for j in range(i):
            checks += 1
            if nums[j] < nums[i]:
                best[i] = max(best[i], best[j] + 1)
    return max(best, default=0), checks

print("length and checks:", lis_slow([3, 1, 4, 2, 5]))
print("length and checks:", lis_slow([10, 9, 2, 5, 3, 7, 101, 18]))

The answers are right. The check count grows with the square of the list length, because every pair is compared once. A long list pays that square in full.

The optimal solution: keep the smallest tail for each length

A tail is the last value of an increasing run, and the method keeps the smallest possible tail for each length found so far in one sorted list. That one list is the whole state.

A new value either extends the list, when it beats every tail, or replaces the first tail that is not smaller than it. A smaller tail leaves more room for later values, and the replacement never changes the list length. Binary search finds the replacement place.

import bisect

def lis_fast(nums):
    tails = []
    for x in nums:
        place = bisect.bisect_left(tails, x)
        if place == len(tails):
            tails.append(x)
        else:
            tails[place] = x
    return len(tails)

cases = [
    ([10, 9, 2, 5, 3, 7, 101, 18], 4),
    ([3, 1, 4, 2, 5], 3),
    ([1, 2, 3, 4], 4),
    ([5, 4, 3, 2, 1], 1),
    ([2, 2, 2], 1),
    ([], 0),
]
for nums, expected in cases:
    result = lis_fast(nums)
    print("nums", nums, "-> length", result, "expected:", expected, "match:", result == expected)

Every case matches. The repeated-values row stays at length 1, because the search finds the first tail not smaller than the value, and an equal value replaces its own slot instead of extending the list.

Walkthrough: tails for 3, 1, 4, 2, 5

The walk feeds one value at a time. Each step prints the tail list after the value lands. The list stays sorted after every step.

import bisect

tails = []
for x in [3, 1, 4, 2, 5]:
    place = bisect.bisect_left(tails, x)
    if place == len(tails):
        tails.append(x)
        action = "append"
    else:
        tails[place] = x
        action = "replace index " + str(place)
    print("value", x, "-", action, "- tails:", tails)
print("longest length:", len(tails))

The final list reads 1, 2, 5, and its length, 3, is the answer the article reads off. The list itself is a set of smallest endings gathered across runs, and the edge section shows a case where those endings never formed one run.

Complexity

Each value costs one binary search over at most n tails, so the time is O(n log n) for n values. The tail list holds at most one entry per value, so the space is O(n).

for n in [5, 10, 20]:
    pairs = n * (n - 1) // 2
    searches = n
    print("values", n, "- pair checks:", pairs, " tail searches:", searches)

At 20 values the pair method makes 190 checks against 20 searches. Each search also stays short, because it halves the tail list at every step.

Edge cases and pitfalls

An empty list has length zero. A falling list has length one, since any single value is a run. A rising list answers its own length.

The classic pitfall reads the tail list as the answer run. The tails are the smallest endings for separate lengths, gathered from different runs. Only the count of tails is the answer.

import bisect

def lis_fast(nums):
    tails = []
    for x in nums:
        place = bisect.bisect_left(tails, x)
        if place == len(tails):
            tails.append(x)
        else:
            tails[place] = x
    return len(tails), tails

print("empty:", lis_fast([]))
print("single:", lis_fast([9]))
print("falling:", lis_fast([5, 4, 3, 2, 1]))
print("rising:", lis_fast([1, 2, 3, 4]))
print("repeats:", lis_fast([2, 2, 2]))
print("tails need not form a run:", lis_fast([2, 6, 3, 4, 1]))

The last row shows the pitfall plainly. Its tails read 1, 3, 4, but the 1 sits at the very end of that input, after the 3 and the 4, so those tails never formed one run. The length is the claim, and the length is what every row proves.