Longest Increasing Subsequence: From n² to n log n

This one is a Medium-rated classic reported from Google, Amazon, Microsoft interviews: "Longest Increasing Subsequence". Like every post in this series, the goal is not memorizing the answer — it is recognizing the Dynamic Programming pattern on sight. Part 7 of 11 in the Dynamic Programming arc.

The Problem

Return the length of the longest strictly increasing subsequence (not necessarily contiguous). A rite-of-passage question: the O(n²) DP is expected within minutes, and the O(n log n) tails construction — patience sorting — is the real interview at Google.

Input:  nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output: 4
One LIS is [2, 3, 7, 101].

Recognizing the Dynamic Programming Pattern

Dynamic programming is recursion with the repetition removed: define the answer to a subproblem, express it in terms of smaller subproblems, and compute each exactly once — top-down with memoization or bottom-up with a table. In interviews the grade hinges on the state definition said out loud ('dp[i] is the best answer using the first i items') far more than on the loop that follows. Most FAANG DP questions are one-dimensional or a small 2D grid — the nine below cover the shapes that repeat.

Classic endpoint-indexed DP: dp[i], the LIS ending at i, maximized over smaller predecessors — O(n²). The upgrade insight: for each length, only the smallest possible tail matters, and those tails form a sorted array — sorted state plus membership updates is a binary search invitation.

The Approach

Maintain tails, where tails[k] is the smallest tail of any increasing subsequence of length k+1. For each value, bisect_left finds its slot: replace the first tail at least as large (improving that length's tail), or append when the value extends beyond every tail. Length of tails is the answer.

Two truths to state unprompted: tails stays sorted (replacement preserves order), and tails is not an actual subsequence — misclaiming that is a known credibility hit. Strictness lives in the bisect flavor: bisect_left for strict, bisect_right for non-decreasing.

Python Solution

import bisect


def length_of_lis(nums: list[int]) -> int:
    """Length of the longest strictly increasing subsequence."""
    tails: list[int] = []              # tails[k]: min tail of a (k+1)-length IS
    for x in nums:
        i = bisect.bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)            # extends the longest so far
        else:
            tails[i] = x               # better (smaller) tail for length i+1
    return len(tails)

Complexity

• Time: O(n log n) — one binary search per element
• Space: O(n) — the tails array

Interview Tips and Follow-Ups

• Recovering the actual subsequence needs predecessor links plus the index history — the tails array alone cannot do it; say so before being asked.
• Russian Doll Envelopes is LIS after sorting by width ascending, height descending — the descending tie-break is the entire trick; a famous Google pairing.
• Explain why replacing mid-array tails never hurts: it only lowers the bar for future extensions. One sentence, big signal.

If this clicked, continue the Dynamic Programming arc in the Technical Interview category. One hundred questions, nine patterns, all in Python.