300. Longest Increasing Subsequence

Longest Increasing Subsequence is the DP problem that has two lives: a clean $O(n^2)$ recurrence that anyone can derive, and a slicker $O(n \log n)$ trick that feels like a magic show until you see the card game behind it. It sits in the dynamic programming pattern family, and the follow-up (can you beat $O(n^2)$?) is where most of the interesting conversation happens.

The problem

Given an integer array, return the length of its longest strictly increasing subsequence — elements picked in order, each larger than the last, not necessarily contiguous. (Full statement on LeetCode.)

For [9, 2, 5, 3, 7, 101, 18] one longest run is 2, 3, 7, 18 (or 2, 3, 7, 101), so the answer is 4. Note “strictly” — [7, 7, 7] has an answer of 1, since equal values can’t extend anything.

Intuition: length of the best chain ending here

Start with the subproblem that makes the recurrence obvious. Let dp[i] be the length of the longest increasing subsequence that ends at index i. Every such subsequence, if it’s longer than one element, has a second-to-last element sitting at some earlier index j with nums[j] < nums[i]. So the best chain ending at i is one more than the best chain ending at any smaller predecessor:

$dp[i] = 1 + \max_{\,j < i,\; nums[j] < nums[i]} dp[j]$

If no such j exists, nums[i] stands alone and dp[i] = 1. The answer is the largest dp[i] over all i, not dp[n-1] — the longest chain can end anywhere, not just at the last element. That single fact trips people up: they return the last cell instead of the max.

To beat quadratic, stop tracking chains and track tails. Keep a list tails where tails[k] holds the smallest possible value that can end an increasing subsequence of length k+1. Walk the array; for each value, find the leftmost tail that isn’t smaller than it and overwrite that slot — or append if the value beats every tail. This is patience sorting: you’re greedily keeping each length’s ending as small as possible so it stays easy to extend. Because tails is always sorted, that “leftmost slot” is a binary search, and its final length is the answer. The tails array itself is not a valid subsequence — only its length is meaningful.

Solution

The $O(n^2)$ DP first, since it reads straight off the recurrence:

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);          // each element alone is a chain of length 1

        int best = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {         // j can precede i
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            best = Math.max(best, dp[i]);        // answer can end at any i
        }
        return best;
    }
}

Now the patience-sort version. The binary search finds the first tails entry >= num (a lower bound), which is exactly the slot that value should replace to keep chains as extendable as possible:

class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] tails = new int[nums.length];
        int size = 0;                            // current length of tails

        for (int num : nums) {
            int lo = 0, hi = size;
            while (lo < hi) {                    // leftmost slot with tails[mid] >= num
                int mid = (lo + hi) >>> 1;
                if (tails[mid] < num) lo = mid + 1;
                else hi = mid;
            }
            tails[lo] = num;                     // overwrite that slot...
            if (lo == size) size++;              // ...or extend if num beat every tail
        }
        return size;
    }
}

Using strict < in the comparison is what keeps it strictly increasing; if the problem allowed equal elements you’d search for the first entry strictly greater instead.

Complexity

Approach	Time	Space
DP (chain ending here)	$O(n^2)$	$O(n)$
Patience sort + binary search	$O(n \log n)$	$O(n)$

The $n \log n$ comes from doing one binary search per element over a tails array that never exceeds length $n$.

In an interview

Write the $O(n^2)$ DP first and say the subproblem out loud: “dp[i] is the longest increasing subsequence ending at i, and I take the best predecessor plus one.” Then name the trap before they ask — the answer is max(dp), not dp[n-1], because the best chain can finish anywhere. That earns the follow-up, and that’s your cue to bring up patience sorting.

For the $O(n \log n)$ version, be honest about what tails is: not the subsequence, just the smallest tail for each length, kept sorted so a binary search places each element. If you can’t reconstruct the exact binary search live, Arrays.binarySearch plus its “insertion point” convention gets you the same lower bound. This “keep the greedily-best endpoint and binary-search into it” idea also underlies problems like Russian Doll Envelopes, and the plain length-of-chain DP shape is the same one behind Coin Change and Word Break. The pattern hub walks through where the 1D-DP recurrence recurs.

References

• LeetCode 300 — Longest Increasing Subsequence