4.23.11 — Longest Increasing Subsequence

LeetCode 300 · Medium · ★ Blind 75

The problem

Return the length of the longest strictly increasing subsequence. A subsequence keeps the original order but may skip elements.

[10,9,2,5,3,7,101,18]   →  4     ([2,3,7,101])
[0,1,0,3,2,3]           →  4     ([0,1,2,3])
[7,7,7,7]               →  1     (strictly increasing, so no repeats)

Up to 2,500 elements. The follow-up asks for O(n \log n).

Subsequence, not subarray — gaps are allowed. That single word rules out sliding windows and rules in DP.

The O(n^2) DP

Let dp[i] be the length of the longest increasing subsequence that ends at index i.

The phrase "ends at" is doing all the work. Without it you cannot extend anything, because you would not know what the last element was.

To compute dp[i], look at every earlier index j. If nums[j] < nums[i], then the subsequence ending at j can be extended by nums[i]:

dp[i] = 1 + \max\{\,dp[j] \ :\ j < i,\ nums[j] < nums[i]\,\}

and dp[i] = 1 if no such j exists — the element alone.

The answer is the maximum over the whole table, not dp[n-1], because the best subsequence may end anywhere. That is the second most common mistake in this problem.

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1] * len(nums)                      # every element alone is length 1

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

        return max(dp)

O(n^2) time, O(n) space. Write this first. It is obviously correct and it is the answer if the follow-up never comes.

The O(n \log n) solution

This one is worth real attention, because the array it maintains is not what people assume.

Keep an array tails, where tails[k] is the smallest possible value that can end an increasing subsequence of length k + 1, among everything seen so far.

For each new number, find the first entry in tails that is greater than or equal to it, and overwrite that entry. If no entry qualifies, append.

Python

import bisect

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []

        for n in nums:
            i = bisect.bisect_left(tails, n)      # first index with tails[i] >= n
            if i == len(tails):
                tails.append(n)                   # extends the longest run
            else:
                tails[i] = n                      # a smaller tail for that length

        return len(tails)

TypeScript

function lengthOfLIS(nums: number[]): number {
  const tails: number[] = [];

  for (const n of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) {                             // first index with tails[i] >= n
      const mid = (lo + hi) >> 1;
      if (tails[mid] < n) lo = mid + 1;
      else hi = mid;
    }
    if (lo === tails.length) tails.push(n);
    else tails[lo] = n;
  }

  return tails.length;
}

The two things people get wrong

tails is not the longest increasing subsequence. Its length is correct; its contents are usually not a real subsequence of the input. It is a set of best-possible endings, one per length. Do not return it as the answer to "give me the subsequence".

Why overwriting is safe. If you can end a length-3 subsequence with 7, and later you find you can end one with 5, then 5 is strictly better — every future number that could extend the 7 can also extend the 5, and some that could not extend 7 can extend 5. Keeping the smaller tail never loses an option.

Why tails stays sorted. A longer subsequence must end at a value at least as large as a shorter one's best ending, so the array is increasing by construction — which is what makes binary search legal.

bisect_left, not bisect_right. bisect_left finds the first entry ≥ n, so an equal value gets overwritten rather than appended, which is what "strictly increasing" requires. Switch to bisect_right and you get the longest non-decreasing subsequence — a one-word change in the problem, a one-function change in the code, and a good thing to point out.

Trace

[10, 9, 2, 5, 3, 7, 101, 18]

n	tails before	action	tails after
10	[]	append	[10]
9	[10]	overwrite index 0	[9]
2	[9]	overwrite index 0	[2]
5	[2]	append	[2,5]
3	[2,5]	overwrite index 1	[2,3]
7	[2,3]	append	[2,3,7]
101	[2,3,7]	append	[2,3,7,101]
18	[2,3,7,101]	overwrite index 3	[2,3,7,18]

Length 4 ✓. Note the final tails is [2,3,7,18], which is a valid subsequence here — but that is luck, not a guarantee.

O(n \log n) time, O(n) space.

Recovering the actual subsequence

If asked for the subsequence rather than its length, keep for each element the index it was placed at in tails, plus a parent pointer to whatever was at the previous position when it was placed. Then walk the parents backwards from the last append.

Say that reconstruction needs extra bookkeeping, because it is the natural follow-up and a lot of people assume tails already is the answer.

Where this goes next

• Russian Doll Envelopes — sort by width ascending and by height descending within equal widths, then run LIS on the heights. The descending tie-break is what stops two envelopes of equal width being nested, and it is the whole trick.
• Number of Longest Increasing Subsequences — count as well as measure, which needs a second table.
• Longest Increasing Path in a Matrix — the grid version, solved with memoised DFS. 4.24.
• Maximum Length of Pair Chain, Longest String Chain — sort first, then LIS.

The pattern to carry: "longest chain under some ordering" is LIS after a sort. Recognising it is what makes Russian Doll Envelopes a five-minute problem instead of a new one.

What the interviewer will push on

"What does dp[i] mean?" The longest increasing subsequence ending at i. The "ending at" is not optional.

"Why is the answer max(dp) and not dp[n-1]?" The best subsequence can end anywhere.

"What does tails hold?" The smallest possible tail for each length. Not an actual subsequence.

"Why is it safe to overwrite?" A smaller tail for the same length dominates a larger one — it can be extended by strictly more values.

"Why is tails sorted?" Longer subsequences need larger endings.

"Strictly increasing or non-decreasing?" bisect_left versus bisect_right.

"Can you return the subsequence itself?" Yes, with parent pointers.

One thing to volunteer: say clearly that tails is not the answer subsequence. It is the single most common misunderstanding of this algorithm, and correcting it unprompted shows you understand what the array is for.

Next: 4.23.12 Partition Equal Subset Sum — knapsack in disguise, and the loop direction that stops an item being reused.