Introduction

The longest increasing subsequence problem asks for the longest subsequence whose values increase strictly from left to right. The subsequence does not need to be contiguous, which is what makes the problem more interesting than a simple sorted run check.

A quadratic dynamic programming solution is easy to understand, but there is a faster O(n log n) method based on binary search. That faster method is the standard approach when the input is large.

Core Idea Behind the O(n log n) Method

The efficient algorithm does not keep every subsequence. Instead, it tracks the smallest possible tail value for an increasing subsequence of each length.

Suppose tails[2] = 7. That means there exists some increasing subsequence of length three ending in 7, and among all such subsequences, 7 is the smallest tail seen so far. A smaller tail is better because it leaves more room for future values to extend the subsequence.

When a new number arrives:

• if it is larger than every tail, append it
• otherwise, replace the first tail greater than or equal to it

The replacement step does not lose the optimal answer. It improves the best tail for that subsequence length.

Length-Only Implementation

Python's bisect_left makes the binary-search step straightforward.

1from bisect import bisect_left
2
3
4def lis_length(values):
5    tails = []
6
7    for value in values:
8        index = bisect_left(tails, value)
9        if index == len(tails):
10            tails.append(value)
11        else:
12            tails[index] = value
13
14    return len(tails)
15
16
17print(lis_length([10, 9, 2, 5, 3, 7, 101, 18]))

This prints 4 because one valid longest increasing subsequence is 2, 3, 7, 18.

Reconstruct the Actual Subsequence

If you need the elements themselves rather than just the length, store predecessor pointers and the array indexes associated with each tail length.

1from bisect import bisect_left
2
3
4def lis(values):
5    tails = []
6    tail_indexes = []
7    previous = [-1] * len(values)
8
9    for i, value in enumerate(values):
10        position = bisect_left(tails, value)
11
12        if position == len(tails):
13            tails.append(value)
14            tail_indexes.append(i)
15        else:
16            tails[position] = value
17            tail_indexes[position] = i
18
19        if position > 0:
20            previous[i] = tail_indexes[position - 1]
21
22    sequence = []
23    k = tail_indexes[-1]
24    while k != -1:
25        sequence.append(values[k])
26        k = previous[k]
27
28    return list(reversed(sequence))
29
30
31print(lis([10, 9, 2, 5, 3, 7, 101, 18]))

The exact subsequence returned depends on replacement decisions, but its length is optimal.

Why the Complexity Is O(n log n)

The algorithm processes each input element once. For each element, it performs a binary search over tails, whose size is at most n. Binary search costs log n, so the full runtime is n * log n.

Space usage is linear because the helper arrays grow in proportion to the input size.

When the Quadratic DP Still Makes Sense

The O(n^2) approach is still useful for teaching, debugging, or very small arrays. It is often easier to derive and extend when you need custom constraints. But once input sizes become large, the binary-search version is the right default.

A good engineering habit is to choose the simpler DP when clarity matters and data is small, then switch to O(n log n) when performance becomes relevant.

Common Pitfalls

• Confusing subsequence with substring or subarray. The chosen elements do not need to be adjacent.
• Using bisect_right for a strictly increasing problem. That changes the behavior for duplicates.
• Assuming the tails array is itself the answer. It tracks best tail values, not necessarily a real subsequence.
• Forgetting predecessor indexes when reconstruction is required. Length-only logic is not enough to recover elements.
• Mixing non-decreasing and strictly increasing definitions. The binary-search condition depends on that choice.

Summary

• The O(n log n) LIS algorithm keeps minimal tail values for each subsequence length.
• Binary search determines where each new element belongs.
• Replacing a tail improves future extension opportunities without losing optimality.
• 'bisect_left is correct for strictly increasing subsequences.'
• Add predecessor tracking if you need the actual subsequence, not just its length.