Dynamic programming · Patience sorting (tails + binary search)

Medium · O(n log n) time · O(n) space

Problem

Given an integer array nums, return the length of the longest strictly increasing subsequence. A subsequence keeps the original order but may skip elements.
Example 1 Input: nums = [10, 9, 2, 5, 3, 7, 101, 18] Output: 4 (for example 2, 3, 7, 18) Example 2 Input: nums = [7, 7, 7, 7] Output: 1 (equal values do not count as increasing)
Constraints 1 ≤ nums.length ≤ 2500 −10^4 ≤ nums[i] ≤ 10^4

Brute force

Imagine a row of numbers. You may cross out as many as you like, but you may not move the rest. What is the longest run you can keep where every number is bigger than the one before it? That kept run is a subsequence.

  1. Keep the original order. You may skip numbers, but never swap them.
  2. Each kept number must be strictly bigger than the previous one, so equal numbers do not count.
  3. Return the length of the longest such run.

The direct idea: for every number, choose to keep it or skip it, and see which choices give the longest run.

The problem with it

Each number has two choices, so n numbers give 2n possibilities. With 2,500 numbers that is hopeless.

How to think your way to the optimal solution

The brute force asks the same small question over and over: "what is the longest run that ends at this number?" Let us answer it once per number. If we know the best run ending at every earlier number, how do we get it for the next one?

Look at the earlier numbers that are smaller than the new one. The new number can be added to any of their runs. So its best run is one more than the best of those. This is the first, simpler solution.

The optimal solution

Approach 1: a table of runs

The idea. Let dp[i] be the longest run that ends exactly at index i. For each i, look at every j before it. If nums[j] < nums[i], the number at i can extend that run.

  1. Start every dp[i] at 1: a number alone is a run of length 1.
  2. For each i, check every earlier j. nums[j] < nums[i]⟶dp[i] = max(dp[i], dp[j] + 1)
  3. The answer is the biggest value in dp.

Cost. For each number we look at all the numbers before it, so this takes O(n²) time and O(n) space. For 2,500 numbers that is fine. It is also a fair answer to give first in an interview. But we can do better.

Approach 2: tails and binary search

The idea. The table keeps far more than we need. Here is a smarter thing to keep. For each run length k, remember only the smallest number that a run of length k can end with. We call this list tails. A small tail is good, because a smaller number is easier to extend.

The list is always sorted. A run of length 3 can always be shortened to a run of length 2 that ends with a smaller number, so the tails never go down as k grows. Because the list is sorted, we can find a place in it with binary search: guess the middle, and the answer ("too small" or "not too small") tells us which half to keep.

What happens to each new number x: find the first tail that is not smaller than x.

  1. Every tail is smaller than x. x is bigger than all of them⟶add x at the end: the longest run grew by one
  2. Some tail is not smaller than x. found it at position k⟶replace it with x: a run of that length can now end lower, and the length does not change
  3. The number of tails at the end is the answer.

By hand, on [10, 9, 2, 5, 3, 7, 101, 18]:

  1. 10. The list is empty, so add it: [10].
  2. 9. The first tail not smaller than 9 is 10. Replace it: [9].
  3. 2. Replace 9: [2].
  4. 5. 5 is bigger than 2, so add it: [2, 5]. The longest run is now 2.
  5. 3. The first tail not smaller than 3 is 5. Replace it: [2, 3].
  6. 7. Bigger than all, so add it: [2, 3, 7].
  7. 101. Add it: [2, 3, 7, 101].
  8. 18. The first tail not smaller than 18 is 101. Replace it: [2, 3, 7, 18].

There are 4 tails, so the answer is 4. Press Play to watch it. The player also has an input of four equal numbers, [7, 7, 7, 7], so you can watch where equal numbers go: they replace a tail, and they never add.

Cost. Each number does one binary search, which takes about log n steps, so the total is O(n log n).

Complexity analysis

ApproachTimeSpace
Try every subsequence2nO(n)
A table of runsO(n²)O(n)
Tails with binary searchO(n log n)O(n)
O(n log n)
Time. Here's why: there are n numbers. Each one does one binary search on the tails list, which is at most n long, so it takes about log n steps. The add or replace afterwards is one step.
O(n)
Space. The tails list never holds more than n numbers. Nothing else grows.

Interviewer follow-ups

These are the questions that usually come next. Open one to see an answer you could say out loud.

"Return the actual subsequence, not just its length."

What they are checkingWhether you know that the tails list is not itself an answer. A common mistake is to print it.

A strong answerThe tails list has the right length, but it can mix numbers from different runs, so it is not always a real subsequence. For example, on [2, 5, 1] the tails become [1, 5], but the 1 comes after the 5 in the array. To get a real one, I remember for each placed number the index of the tail just before it (its "previous" pointer), and also which index sits in each tail slot. At the end I start from the last slot and follow the pointers backwards.

"Now equal numbers are allowed: find the longest non-decreasing run."

What they are checkingWhether you know exactly which line decides "strictly" and can change it with confidence.

A strong answerOne comparison changes. Now a tail that is equal to x can still be extended by x, so I look for the first tail that is bigger than x, not "not smaller". In code, tails[mid] < x becomes tails[mid] <= x (in Python, bisect_right instead of bisect_left). On [7, 7, 7, 7] the answer changes from 1 to 4.

"Why is it safe to replace a tail? You are throwing information away."

What they are checkingWhether you understand why the trick is correct, or only memorised it.

A strong answerReplacing a tail with a smaller number never hurts. A run of that length that ends lower can be extended by every number that the old run could extend, and by more. The old, larger tail has no future that the new one lacks. And we do not lose the length: the length of the list only grows when a number is bigger than every tail, which is exactly when a longer run exists.

Spot this pattern