Longest Increasing Subsequence: O(n²) DP and the O(n log n) Upgrade

You have an array of integers. Find the longest increasing subsequence (LIS): the longest chain of elements that appear left-to-right in the original array and are strictly increasing. That's it. One sentence. Simple to state, annoying to optimize, and somehow it's LeetCode 300.

The thing that makes this problem interview gold isn't the question. It's that it has two completely different clean solutions that share almost nothing in common. One uses dynamic programming. The other uses binary search. Both work. Understanding both is worth a meaningful chunk of your prep time because they cover two separate algorithmic ideas in one problem.

LeetCode 300 is the canonical version. If you can explain both approaches, you're in good shape.

Subsequence Is Not the Same as Substring

A substring must be contiguous. A subsequence just has to preserve relative order. You can skip elements freely.

In [3, 1, 4, 1, 5, 9, 2, 6], the elements at indices 1, 2, 4, 5 give you [1, 4, 5, 9]. Not contiguous. But they appear left-to-right in the original array and each one is strictly greater than the previous. That's a valid increasing subsequence.

Walk Through a Real Example First

Take [10, 9, 2, 5, 3, 7, 101, 18]. The LIS length is 4.

Two valid answers exist: [2, 5, 7, 101] and [2, 3, 7, 101]. Both length 4. No subsequence of length 5 exists in this array.

Build the intuition by hand. Starting from 2 at index 2, the longest forward chain is 2 → 5 → 7 → 101 or 2 → 3 → 7 → 101. No other starting element beats length 4. That's the answer.

Why Brute Force Can't Solve the Longest Increasing Subsequence

For each element, you either include it or skip it. That's 2^n possible subsets to generate and check. At n = 50, that's roughly a quadrillion operations. Your laptop would finish sometime around the heat death of the universe.

You need dynamic programming.

O(n²) DP: The Solution That Builds the Right Mental Model

Define dp[i] as the length of the longest increasing subsequence that ends at index i.

Every element is a valid LIS of length 1 by itself, so dp starts as all 1s. For each position i, scan every j < i. If nums[j] < nums[i], then you can extend whatever LIS ended at j by appending nums[i]. Take the max across all valid j.

def length_of_lis(nums: list[int]) -> int:
    dp = [1] * len(nums)

    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

Tracing through [10, 9, 2, 5, 3, 7, 101, 18]:

i	nums[i]	dp[i]	reason
0	10	1	base case
1	9	1	10 > 9, no valid j
2	2	1	10 > 2 and 9 > 2, no valid j
3	5	2	extends from index 2 (2 < 5)
4	3	2	extends from index 2 (2 < 3)
5	7	3	extends from index 3 or 4 (5 or 3 < 7)
6	101	4	extends from index 5 (7 < 101)
7	18	4	extends from index 5 (7 < 18)

max(dp) = 4. Correct.

Time: O(n²). Space: O(n). This passes most interview constraints comfortably. If you want the full picture of why DP problems decompose this way, the dynamic programming framework breaks down the pattern behind all of them.

But there is a faster solution, and the jump from O(n²) to O(n log n) is exactly the kind of insight interviewers probe for.

O(n log n): The Patience Sort Trick

This version shows up in interviews because it's non-obvious, memorable once you see it, and easy to get completely wrong under pressure. The original idea traces back to patience sorting, an algorithm for a card game. You are not expected to know that. You are expected to know what the tails array represents, which is the part that trips people up.

Maintain a "tails" array where tails[k] is the smallest possible tail element of any increasing subsequence of length k + 1.

For each new element x:

Binary search tails for the leftmost position where tails[pos] >= x
If that position is at the end: append x (you just extended the longest subsequence found so far)
Otherwise: replace tails[pos] with x (maintaining a smaller tail for that length, keeping future options open)

The LIS length is len(tails) when you finish.

Trace through [10, 9, 2, 5, 3, 7, 101, 18] step by step:

Process 10:  tails = [10]
Process 9:   tails = [9]            (9 replaces 10, smaller tail for length 1)
Process 2:   tails = [2]            (2 replaces 9)
Process 5:   tails = [2, 5]         (5 appends, extends to length 2)
Process 3:   tails = [2, 3]         (3 replaces 5, smaller tail for length 2)
Process 7:   tails = [2, 3, 7]      (7 appends, extends to length 3)
Process 101: tails = [2, 3, 7, 101] (101 appends, extends to length 4)
Process 18:  tails = [2, 3, 7, 18]  (18 replaces 101, smaller tail for length 4)

len(tails) = 4. Correct.

The tails array stays sorted throughout. Each element either extends the right end or replaces something in the middle with an equal-or-smaller value. The sorted property is what makes binary search valid here. The binary search invariant guide covers why maintaining sorted order is the key to making this work at all.

import bisect

def length_of_lis(nums: list[int]) -> int:
    tails: list[int] = []
    for x in nums:
        pos = bisect.bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)

Time: O(n log n). Space: O(n).

tails Is Not the Actual LIS

After processing [10, 9, 2, 5, 3, 7, 101, 18], tails is [2, 3, 7, 18]. Go look at the original array. There is no increasing subsequence [2, 3, 7, 18] in there. The 18 replaced the 101 during bookkeeping and then stayed. The actual LIS is [2, 3, 7, 101] or [2, 5, 7, 101]. This is the moment in most people's first trace where they go back and assume they made an error. They didn't.

tails tracks what's possible, not what's actual. It is a bookkeeping structure. The length is correct. The elements themselves are an artifact of the algorithm's replacements.

Most interview problems only ask for the length, so this is rarely a problem in practice. If you need to reconstruct the actual sequence, you maintain a separate parent-pointer array tracking which element each new entry extends, then walk back from the final element in tails. That reconstruction is genuinely tricky and usually only comes up in harder variants.

One Structure, Every Language

The O(n log n) solution in all 14 major interview languages. Every version uses bisect_left semantics: find the leftmost position where tails[pos] >= x. For strictly increasing subsequences, this is the correct bound.

# Python 3
import bisect

def length_of_lis(nums: list[int]) -> int:
    tails: list[int] = []
    for x in nums:
        pos = bisect.bisect_left(tails, x)
        if pos == len(tails):
            tails.append(x)
        else:
            tails[pos] = x
    return len(tails)

# Python 2
import bisect

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

// JavaScript
function lengthOfLIS(nums) {
    const tails = [];
    for (const x of nums) {
        let lo = 0, hi = tails.length;
        while (lo < hi) {
            const mid = (lo + hi) >>> 1;
            if (tails[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        if (lo === tails.length) tails.push(x);
        else tails[lo] = x;
    }
    return tails.length;
}

// TypeScript
function lengthOfLIS(nums: number[]): number {
    const tails: number[] = [];
    for (const x of nums) {
        let lo = 0, hi = tails.length;
        while (lo < hi) {
            const mid = (lo + hi) >>> 1;
            if (tails[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        if (lo === tails.length) tails.push(x);
        else tails[lo] = x;
    }
    return tails.length;
}

// Java
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;
            while (lo < hi) {
                int mid = lo + (hi - lo) / 2;
                if (tails[mid] < x) lo = mid + 1;
                else hi = mid;
            }
            tails[lo] = x;
            if (lo == size) size++;
        }
        return size;
    }
}

// C++
#include <algorithm>
#include <vector>

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

// C
#include <stdlib.h>

int lengthOfLIS(int* nums, int n) {
    int* tails = (int*)malloc(n * sizeof(int));
    int size = 0;
    for (int i = 0; i < n; i++) {
        int lo = 0, hi = size;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (tails[mid] < nums[i]) lo = mid + 1;
            else hi = mid;
        }
        tails[lo] = nums[i];
        if (lo == size) size++;
    }
    free(tails);
    return size;
}

// Go
import "sort"

func lengthOfLIS(nums []int) int {
    tails := []int{}
    for _, x := range nums {
        pos := sort.SearchInts(tails, x)
        if pos == len(tails) {
            tails = append(tails, x)
        } else {
            tails[pos] = x
        }
    }
    return len(tails)
}

// Rust
fn length_of_lis(nums: Vec<i32>) -> i32 {
    let mut tails: Vec<i32> = Vec::new();
    for x in nums {
        let pos = tails.partition_point(|&t| t < x);
        if pos == tails.len() {
            tails.push(x);
        } else {
            tails[pos] = x;
        }
    }
    tails.len() as i32
}

// Swift
func lengthOfLIS(_ nums: [Int]) -> Int {
    var tails = [Int]()
    for x in nums {
        var lo = 0, hi = tails.count
        while lo < hi {
            let mid = lo + (hi - lo) / 2
            if tails[mid] < x { lo = mid + 1 }
            else { hi = mid }
        }
        if lo == tails.count { tails.append(x) }
        else { tails[lo] = x }
    }
    return tails.count
}

// Kotlin
fun lengthOfLIS(nums: IntArray): Int {
    val tails = mutableListOf<Int>()
    for (x in nums) {
        var lo = 0
        var hi = tails.size
        while (lo < hi) {
            val mid = lo + (hi - lo) / 2
            if (tails[mid] < x) lo = mid + 1
            else hi = mid
        }
        if (lo == tails.size) tails.add(x)
        else tails[lo] = x
    }
    return tails.size
}

// C#
public int LengthOfLIS(int[] nums) {
    var tails = new List<int>();
    foreach (int x in nums) {
        int lo = 0, hi = tails.Count;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (tails[mid] < x) lo = mid + 1;
            else hi = mid;
        }
        if (lo == tails.Count) tails.Add(x);
        else tails[lo] = x;
    }
    return tails.Count;
}

# Ruby
def length_of_lis(nums)
    tails = []
    nums.each do |x|
        lo, hi = 0, tails.length
        while lo < hi
            mid = lo + (hi - lo) / 2
            if tails[mid] < x
                lo = mid + 1
            else
                hi = mid
            end
        end
        if lo == tails.length
            tails << x
        else
            tails[lo] = x
        end
    end
    tails.length
end

// PHP
function lengthOfLIS(array $nums): int {
    $tails = [];
    foreach ($nums as $x) {
        $lo = 0;
        $hi = count($tails);
        while ($lo < $hi) {
            $mid = intdiv($lo + $hi, 2);
            if ($tails[$mid] < $x) $lo = $mid + 1;
            else $hi = $mid;
        }
        if ($lo === count($tails)) $tails[] = $x;
        else $tails[$lo] = $x;
    }
    return count($tails);
}

Why Every Interviewer Likes This Problem

The jump from O(n²) to O(n log n) requires genuine insight, not pattern matching. Most candidates who've studied DP know the quadratic solution. Fewer can derive the binary search approach from scratch and explain why it works. That gap is exactly what differentiates candidates at the margin.

LIS also has clean variants that test depth. Once you know LeetCode 300, an interviewer can extend to counting the number of distinct LIS (LeetCode 673), or to Russian Doll Envelopes (LeetCode 354). Envelopes is LIS in two dimensions with a sort trick: sort by width ascending, height descending for ties, then run LIS on heights alone. The tie-breaking direction is the most important detail, completely non-obvious, and it has ended a lot of otherwise good interviews early.

A candidate who walks through the O(n²) DP table and then derives the O(n log n) approach in a single session is demonstrating optimization instinct, not just memorization. That's a lot of signal for one problem. The interviewer has now watched you build DP state, explain recurrences, and then tear all of it down and find a better structure entirely.

Practicing that narration out loud is what most engineers skip. SpaceComplexity runs voice-based mock interviews with rubric feedback for exactly that gap: explaining a solution as you code it, not just producing a correct answer.

For DP problems that follow the same subproblem decomposition logic as LIS, the dynamic programming framework covers the pattern behind all of them.

The Mistakes That Give You a Wrong Length

Using bisect_right instead of bisect_left. If you use upper_bound semantics, you allow equal elements in the subsequence. That gives you the longest non-decreasing subsequence instead of strictly increasing. One character off. Completely different problem. This looks totally fine when you test it on sorted input, then crumbles the moment the interviewer adds [2, 2, 2] to your test case.

Assuming tails represents the actual LIS. It doesn't. After the final step above, tails is [2, 3, 7, 18] but 18 was never part of any LIS of length 4. The array is a bookkeeping artifact. Use it for length only.

Returning dp[n-1] instead of max(dp) in the O(n²) version. dp[i] is the LIS length ending at index i, not the global best up to i. The last element might not be part of the optimal LIS at all. In [1, 2, 3, 0], dp[3] is 1 and the answer is 3. Returning dp[n-1] loses you the problem on that input. You need to scan the entire dp array.