Two Ways to Find the Longest Increasing Subsequence — and Why O(n log n) Works

LeetCode 300 asks for the length of the longest strictly increasing subsequence of an integer array. Subsequence, not subarray — elements don't need to be adjacent, but they must appear in their original relative order, and each element must be strictly greater than the last.

The canonical example is [10, 9, 2, 5, 3, 7, 101, 18], where the answer is 4 because [2, 3, 7, 101] is the longest strictly increasing subsequence you can pull from it (among several others of the same length: [2, 5, 7, 101], [2, 3, 7, 18]).

This problem sits at the intersection of DP and binary search in a way that most subsequence problems don't. The O(n²) DP gives you the right intuition about state. The O(n log n) binary search variant gives you something more interesting: a greedy invariant that's non-obvious until you stare at it long enough.

What the constraints force

n can be up to 2500. That puts O(n²) at about 6.25 million operations — fast enough, comfortably under any reasonable time limit. An O(n³) approach would already be borderline. Pure exponential brute force (trying every subsequence) is 2^2500, which is meaningless.

So n = 2500 is not the constraint that rules out naive exponential search; it's the constraint that makes O(n²) acceptable and makes O(n log n) a follow-up optimization rather than a requirement. That changes how you think about this problem: the O(n²) DP is a perfectly valid interview answer, not a stepping stone to dismiss.

Values are bounded between -10^4 and 10^4. That doesn't change anything algorithmically here — no modular arithmetic, no overflow concern, no bucketing trick. It just means you don't need to worry about using element values as dictionary keys.

O(n²) DP: the natural formulation

The state definition makes the recurrence self-evident. Let dp[i] be the length of the longest increasing subsequence that ends exactly at index i. Every element forms a subsequence of length 1 by itself, so dp[i] = 1 is the baseline for all i.

To compute dp[i], scan every index j < i. If nums[j] < nums[i], you can extend any LIS ending at j by appending nums[i]. So dp[i] = max(dp[i], dp[j] + 1) whenever nums[j] < nums[i].

The answer is max(dp) — the maximum over all ending positions.

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

public class Solution {
    public int LengthOfLIS(int[] nums) {
        int n = nums.Length;
        int[] dp = new int[n];
        Array.Fill(dp, 1);
 
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.Max(dp[i], dp[j] + 1);
                }
            }
        }
 
        return dp.Max();
    }
}

Let me trace through [10, 9, 2, 5, 3, 7, 101, 18] step by step.

Initial: dp = [1, 1, 1, 1, 1, 1, 1, 1]
         idx:  0  1  2  3  4  5  6  7

i=1 (val=9):  j=0, nums[0]=10 >= 9, skip.  dp[1]=1
i=2 (val=2):  j=0, 10>=2 skip; j=1, 9>=2 skip.  dp[2]=1
i=3 (val=5):  j=0, 10>=5 skip; j=1, 9>=5 skip; j=2, 2<5 -> dp[3]=max(1,dp[2]+1)=2.  dp[3]=2
i=4 (val=3):  j=0,1 skip; j=2, 2<3 -> dp[4]=max(1,2)=2; j=3, 5>=3 skip.  dp[4]=2
i=5 (val=7):  j=2, 2<7 -> dp[5]=max(1,2)=2; j=3, 5<7 -> dp[5]=max(2,3)=3; j=4, 3<7 -> dp[5]=max(3,3)=3.  dp[5]=3
i=6 (val=101): all previous < 101. dp[6]=max over all j of dp[j]+1 = dp[5]+1=4.  dp[6]=4
i=7 (val=18):  j=2,3,4,5 < 18; dp[7]=max(dp[2]+1,dp[3]+1,dp[4]+1,dp[5]+1)=max(2,3,3,4)=4.  dp[7]=4

dp = [1, 1, 1, 2, 2, 3, 4, 4]
max(dp) = 4

The trace shows something worth noticing: indices 6 and 7 both give length 4. That's because both [2,3,7,101] and [2,3,7,18] have length 4. The dp array captures the length of the best LIS ending at each position — not a unique subsequence.

Time: O(n²). Space: O(n) for the dp array.

O(n log n): the patience-sorting insight

The follow-up asks if you can do O(n log n). The approach that achieves it uses a greedy invariant called patience sorting, and it's worth understanding why it works rather than just memorizing the code.

Maintain an array tails where tails[k] holds the smallest possible tail value of any increasing subsequence of length k + 1 seen so far. That last phrase is the key: it's not the tail of one specific subsequence — it's the minimum tail across all optimal-length subsequences of that length. Smaller tails are better because they leave more room for future elements to extend the sequence.

For each new element num:

• If num is larger than everything in tails, it extends the longest subsequence seen so far. Append it.
• Otherwise, find the leftmost position in tails where tails[pos] >= num. Replace tails[pos] with num. This doesn't destroy a subsequence — it just records that there now exists a length-(pos+1) subsequence with a smaller tail, which is strictly better.

tails always stays sorted (which is why binary search works on it), and its length at the end equals the LIS length. Note: tails itself is not necessarily a valid subsequence from nums — it's a bookkeeping structure, not a reconstruction of the actual LIS.

Each bisect_left call finds the insertion point in O(log n), and we process n elements — total O(n log n).

import bisect
 
class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        tails: list[int] = []
 
        for num in nums:
            pos = bisect.bisect_left(tails, num)
            if pos == len(tails):
                tails.append(num)
            else:
                tails[pos] = num
 
        return len(tails)

public class Solution {
    public int LengthOfLIS(int[] nums) {
        var tails = new List<int>();
 
        foreach (int num in nums) {
            int pos = BinarySearchLeft(tails, num);
            if (pos == tails.Count) {
                tails.Add(num);
            } else {
                tails[pos] = num;
            }
        }
 
        return tails.Count;
    }
 
    private static int BinarySearchLeft(List<int> arr, int target) {
        int left = 0, right = arr.Count;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] < target) left = mid + 1;
            else right = mid;
        }
        return left;
    }
}

The C# version manually implements bisect_left since there's no built-in equivalent in List<T>. Array.BinarySearch returns a bitwise complement for "not found" positions, which is usable but ugly; the manual implementation is clearer.

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

Why the greedy invariant holds

The invariant that tails is always sorted is not obvious at first — let me show why replacement preserves it.

Before processing num, tails is sorted: tails[0] < tails[1] < ... < tails[k]. We find pos such that tails[pos] >= num and tails[pos-1] < num (or pos = 0). We replace tails[pos] with num. After replacement:

• tails[pos-1] < num (if pos > 0): true by definition of pos.
• num <= tails[pos] (the original): we replaced with something smaller or equal.
• tails[pos] <= tails[pos+1] (next position): num <= tails[pos] < tails[pos+1], so this holds.

So the sorted invariant is preserved. And since tails is always sorted, binary search is always valid. The invariant bootstraps itself.

Edge cases that actually matter

Single element: nums = [5]. The outer loop processes one element, appends it to tails, returns len(tails) = 1. Both approaches handle this — the DP inner loop is empty for i=0, baseline is 1.

All elements equal: nums = [7, 7, 7, 7, 7, 7, 7]. Strictly increasing means equal elements cannot extend a subsequence. In the DP, nums[j] < nums[i] is false everywhere, so every dp[i] stays at 1. In the binary search approach, bisect_left finds position 0 for every 7 (since tails[0] = 7 >= 7), so we keep replacing position 0. tails stays length 1. Answer: 1.

Strictly decreasing: nums = [5, 4, 3, 2, 1]. In the DP, each new element is smaller than all previous ones, so no extension happens. In the binary search approach, each element replaces position 0. Final tails = [1], length 1.

Already sorted ascending: nums = [1, 2, 3, 4, 5]. Every element appends to tails. Final length 5. In the DP, each dp[i] = i + 1. Correct.

Two elements where first is larger: nums = [3, 1]. DP: dp[0]=1, dp[1]=1 (3 >= 1). Binary search: tails=[3], then 1 replaces position 0 -> tails=[1], length 1. Answer: 1.

Approach comparison

The space is O(n) for both. Neither is reducible: the DP needs to store all dp[i] values, and the binary search needs tails up to length n.

The two-lookback DP pattern

This problem sits next to Coin Change (LeetCode 322) in this series, but the DP state is fundamentally different. Coin Change defines dp[i] over amounts — a scalar target. LIS defines dp[i] over array positions — the state depends on where you are in the input, not just a count.

That position-indexed DP with a "best value ending here" formulation appears in several other problems. LeetCode 152 (Maximum Product Subarray) tracks both the maximum and minimum product ending at each index because negatives can flip signs — it's the same lookback idea but with two tracked values instead of one. LeetCode 673 (Number of LIS) asks how many distinct longest increasing subsequences exist — you extend the DP table with a count array alongside the length array, so dp[i] becomes a pair (length, count). LeetCode 354 (Russian Doll Envelopes) reduces to LIS after sorting envelopes by width ascending and height descending, then running LIS on heights — the reduction is the clever part.

The binary search approach here generalizes to LeetCode 354 directly: once you have the O(n log n) binary search version working, Russian Doll Envelopes is just a sort away from the same solution.

I'd ship the O(n²) DP for most interview contexts — the code is four lines, the logic is self-evident, and it handles every edge case without binary search subtleties. The O(n log n) version is worth knowing because the patience-sorting invariant is genuinely elegant, and the same bisect_left trick appears in other problems where maintaining a sorted structure unlocks a better complexity class.