LeetCode 300 Longest Increasing Subsequence: O(n²) DP, O(n log n) Patience Sorting and Reconstruction

Longest Increasing Subsequence is one of the few problems where interviewers routinely ask for two solutions. The O(n²) DP checks whether you can define a state and a transition. The O(n log n) version checks whether you can reason about an invariant, since the code is short but nobody accepts it without an explanation of why a greedy-looking replacement gives the right length.

This page builds both with dry runs, shows the card game (patience sorting) that makes the fast version intuitive, explains how to recover the actual sequence, and covers the variants interviewers use as follow-ups. It assumes you've seen basic DP; if not, start with Coin Change, which walks through the recursion-to-table process in detail.

The Problem: Longest Strictly Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence is derived by deleting zero or more elements without changing the order of the rest.

Constraints on LeetCode: 1 ≤ nums.length ≤ 2500, values between −10⁴ and 10⁴. The follow-up asks for O(n log n). With n = 2500, O(n²) is about 6 million steps and passes easily, so on the platform both work; in an interview, the follow-up is where the real discussion happens.

Two things to clarify up front: strictly increasing (so [7, 7] has LIS 1), and subsequence, not subarray (elements needn't be adjacent). The contiguous version, "longest increasing subarray", is a trivial O(n) scan.

Brute force

Each element is either in or out, so there are 2ⁿ subsequences. Checking each is hopeless beyond n ≈ 25. The recursion "take or skip each element, remembering the last taken value" has overlapping subproblems, which is the cue for DP.

The O(n²) Dynamic Programming Solution

Choosing the state

The natural state "LIS of the first i elements" doesn't work on its own, because to extend a subsequence you need to know its last value. So pin the last element instead:

dp[i] = length of the longest increasing subsequence that ends exactly at index i.

Any increasing subsequence ending at i is either just [nums[i]], or some increasing subsequence ending at an earlier j with nums[j] < nums[i], followed by nums[i]. Take the best such j:

The answer is the max over all i, not dp[n−1], because the LIS doesn't have to end at the last element. That's the most common bug in this version.

Dry run on [10, 9, 2, 5, 3, 7, 101, 18]

Max of dp is 4. Note 18 can't extend 101, so dp[7] comes from 7 instead.

from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
        return max(dp)

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size(), best = 1;
        vector<int> dp(n, 1);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j)
                if (nums[j] < nums[i]) dp[i] = max(dp[i], dp[j] + 1);
            best = max(best, dp[i]);
        }
        return best;
    }
};

This version is worth writing first in an interview even if you know the faster one. It's easy to verify, it generalises to many variants (counting LIS, largest divisible subset, pair chains), and it's what you fall back to when the comparison isn't a simple "less than".

The O(n log n) Tails Array

The idea

The O(n²) DP asks, for each new element, "which earlier subsequence can I extend?" and scans everything. But many earlier subsequences are redundant. If two increasing subsequences have the same length, the one with the smaller last element is always at least as useful, since anything that extends the other also extends it.

So for each length, remember only the best (smallest) possible tail:

tails[k] = the smallest last element of any increasing subsequence of length k + 1 seen so far.

The update rule

For each new element x:

1. Find the first index k where tails[k] ≥ x (binary search).
2. If no such k (x is bigger than every tail), x extends the longest subsequence: append it. The LIS length grew by one.
3. Otherwise set tails[k] = x. The subsequence ending at tails[k − 1] (which is < x) extended by x has length k + 1 and a smaller tail than before.

The answer is len(tails).

Why tails stays sorted (so binary search is valid)

Claim: tails is strictly increasing at all times. Any increasing subsequence of length k + 2 contains, as its first k + 1 elements, an increasing subsequence of length k + 1 whose last element is smaller than the full sequence's tail. So the best tail for length k + 1 is strictly smaller than the best tail for length k + 2. The update preserves this: we replace tails[k] with an x that is > tails[k − 1] (because k is the first position with tail ≥ x) and ≤ the old tails[k] < tails[k + 1].

Dry run on [10, 9, 2, 5, 3, 7, 101, 18]

Length 4. Here the final tails happens to be a valid LIS, but that's a coincidence.

Why It Works: The Patience Sorting Connection

The tails algorithm is a card game in disguise. Deal the numbers one at a time like cards. Each card goes on the leftmost pile whose top card is ≥ it; if no pile qualifies, start a new pile on the right. This is patience sorting (named after the solitaire game).

The pile tops are exactly the tails array. And the number of piles equals the LIS length, for two reasons that together form a neat proof:

• LIS ≤ number of piles. Within a pile, cards are placed on top only if they're ≤ the current top, so each pile is non-increasing from bottom to top in deal order. An increasing subsequence can use at most one card from each pile. So it can't be longer than the number of piles.
• LIS ≥ number of piles. When a card goes on pile k, the top of pile k − 1 at that moment is smaller than it (otherwise it would have gone there). Link each card to that top. Following links back from any card on the last pile gives an increasing subsequence with one card per pile.

That second argument is also the recipe for reconstruction: the "link" is a parent pointer. If an interviewer asks "why should I believe the tails trick?", the patience sorting picture plus these two bullets is a complete, short answer.

O(n log n) Code in Python, C++ and Java

from bisect import bisect_left
from typing import List

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []
        for x in nums:
            k = bisect_left(tails, x)      # first tail >= x
            if k == len(tails):
                tails.append(x)
            else:
                tails[k] = x
        return len(tails)

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> tails;
        for (int x : nums) {
            auto it = lower_bound(tails.begin(), tails.end(), x);   // first >= x
            if (it == tails.end()) tails.push_back(x);
            else *it = x;
        }
        return tails.size();
    }
};

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;
        for (int x : nums) {
            int lo = 0, hi = size;               // search in tails[0..size)
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if (tails[mid] < x) lo = mid + 1;
                else hi = mid;
            }
            tails[lo] = x;                       // replace or append
            if (lo == size) size++;
        }
        return size;
    }
}

In Java, writing the binary search by hand is clearer than Arrays.binarySearch, whose return value for missing keys (−(insertion point) − 1) and unspecified behaviour with duplicates are easy to misuse. The hand-written loop is the standard "lower bound" template from the binary search patterns guide.

Strict vs non-decreasing

For [7, 7, 7], bisect_left keeps replacing index 0, giving length 1 (strict). bisect_right appends each 7, giving length 3 (non-decreasing). LeetCode 1964 (Longest Obstacle Course at Each Position) is the non-decreasing version and reports the length ending at every index, which is just k + 1 at each step.

Complexity

The binary search runs over tails, which never exceeds the LIS length L, so the bound is really O(n log L). Mentioning that tighter bound is a small but nice signal.

Reconstructing the Actual Sequence

From the O(n²) DP

Keep parent[i] = the j that gave dp[i] its value. Start from the index with the largest dp and follow parents.

def lis_quadratic_with_path(nums):
    n = len(nums)
    dp, parent = [1] * n, [-1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i] and dp[j] + 1 > dp[i]:
                dp[i], parent[i] = dp[j] + 1, j
    k = max(range(n), key=lambda i: dp[i])
    seq = []
    while k != -1:
        seq.append(nums[k])
        k = parent[k]
    return seq[::-1]

From the O(n log n) method

Store indices in tails instead of values, and when placing element i at position k, set its parent to the index currently at position k − 1. That's exactly the "link to the top of the previous pile" from the patience-sorting proof.

def lis_sequence(nums):
    tails_idx = []                 # tails_idx[k] = index of the best tail for length k + 1
    parent = [-1] * len(nums)
    for i, x in enumerate(nums):
        lo, hi = 0, len(tails_idx)
        while lo < hi:             # first k with nums[tails_idx[k]] >= x
            mid = (lo + hi) // 2
            if nums[tails_idx[mid]] < x:
                lo = mid + 1
            else:
                hi = mid
        if lo > 0:
            parent[i] = tails_idx[lo - 1]
        if lo == len(tails_idx):
            tails_idx.append(i)
        else:
            tails_idx[lo] = i
    seq, k = [], tails_idx[-1] if tails_idx else -1
    while k != -1:
        seq.append(nums[k])
        k = parent[k]
    return seq[::-1]

# lis_sequence([3, 4, 5, 1]) -> [3, 4, 5]
# lis_sequence([10, 9, 2, 5, 3, 7, 101, 18]) -> [2, 3, 7, 18]

Why is the parent chain valid? When i was placed at position k, the element at tails_idx[k − 1] came earlier in the array and had a smaller value, and it was itself the end of a valid length-k chain at that moment. Later replacements in tails_idx don't change already-recorded parents, so each chain stays intact.

LIS Variants Interviewers Ask

Number of Longest Increasing Subsequences (LeetCode 673)

Extend the O(n²) DP with a count array.

def find_number_of_lis(nums):
    n = len(nums)
    length, count = [1] * n, [1] * n
    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                if length[j] + 1 > length[i]:
                    length[i], count[i] = length[j] + 1, count[j]
                elif length[j] + 1 == length[i]:
                    count[i] += count[j]
    best = max(length)
    return sum(c for l, c in zip(length, count) if l == best)

# [1, 3, 5, 4, 7] -> 2   ([1,3,4,7] and [1,3,5,7])

An O(n log n) version exists using a Fenwick or segment tree keyed by value that stores (best length, count) pairs, which is a good thing to mention if pushed.

Russian Doll Envelopes (LeetCode 354)

Envelope (w, h) fits inside (W, H) if w < W and h < H. Find the longest nesting chain. Sort by width ascending and, for equal widths, height descending, then run the strict O(n log n) LIS on heights. The descending tie-break makes envelopes with the same width impossible to chain, because their heights then appear in decreasing order.

from bisect import bisect_left

def max_envelopes(envelopes):
    envelopes.sort(key=lambda e: (e[0], -e[1]))
    tails = []
    for _, h in envelopes:
        k = bisect_left(tails, h)
        if k == len(tails):
            tails.append(h)
        else:
            tails[k] = h
    return len(tails)

# [[5,4],[6,4],[6,7],[2,3]] -> 3   ([2,3] -> [5,4] -> [6,7])

n can reach 10⁵ here, so the O(n²) DP times out. This is the problem where the fast version is mandatory.

More of the family

The last row is a lovely trick: LCS is normally O(n·m) (see DP on strings), but when both sequences are permutations of the same values, it reduces to LIS. Another alternative for LIS itself is a Fenwick tree over compressed values that answers "best dp among values < x" in O(log n), which generalises to weighted versions where the tails trick doesn't apply.

How LIS Shows Up in Interviews

LIS is commonly reported at Google, Amazon, Microsoft and in Indian product-company DP rounds. It's typically used to check two levels of skill, so plan your time for both.

1. Clarify: strictly increasing or non-decreasing? Length or the sequence itself? Size of n?
2. O(n²) first (5–7 minutes): define dp[i] as "ending at i", write the recurrence, point out the answer is the max over i.
3. Bridge to O(n log n): "For the same length, only the smallest tail matters. If I keep the best tail per length, that array is sorted, so I can binary search."
4. Prove it briefly: sortedness argument, or the patience sorting two-bullet proof.
5. Dry run [3, 4, 5, 1] and point out tails isn't the LIS. Volunteering that is a strong signal.

Follow-ups to expect

• "Print the LIS." Parent pointers on indices.
• "Non-decreasing instead?" Switch to upper_bound.
• "Count them." LeetCode 673 DP.
• "2D version." Russian Doll with the descending tie-break.
• "Elements arrive in a stream; report LIS length after each." The tails method already works online: O(log n) per element.

Common Mistakes

• Returning dp[n − 1] instead of max(dp) in the O(n²) version.
• Using bisect_right for the strict problem. [7, 7, 7] returns 3 instead of 1.
• Treating tails as the answer sequence. Fails on [3, 4, 5, 1].
• Russian Doll with ascending height tie-break. [[1,1],[1,2]] would chain two same-width envelopes.
• Confusing subsequence with subarray. A sliding window won't help here.
• Binary search bounds. Search [0, size) with hi = size, so "append" is the case lo == size.

LIS sits alongside Word Break and Coin Change as one of the core 1D DP problems. If you can explain why only the smallest tail per length matters, you've learned a technique (dominance pruning: discard states that are never better) that also shows up in scheduling, knapsack optimisations and many contest problems. The DP interview questions guide lists where to go next.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.