Longest Increasing Subsequence

The problem

Given a list of whole numbers nums, return the length of its longest strictly increasing subsequence. A subsequence is what remains when you delete any of the numbers, possibly none, and keep the others in their original order, so its numbers do not have to be neighbors. Strictly increasing means each number is larger than the one before it; equal numbers do not count. A single number is an increasing subsequence of length 1.

What to write

function solve(nums: number[]): number

Input
nums = [10,9,2,5,3,7,101,18]

Output
4

Input
nums = [0,1,0,3,2,3]

Output
4

Constraints

1 ≤ nums.length ≤ 2500.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   There can be 2,500 numbers, and each one is either in a subsequence or left out, so there are far too many subsequences to try them all. Note also that strictly increasing means two equal numbers can never both be picked.

2. Hint 2: Ask a smaller question

   Inside 0, 1, 0, 3, 2 there are two increasing subsequences of three numbers: 0, 1, 3 and 0, 1, 2. The next number is 3. Which of the two can it extend, and why? If you could remember only one of them, which would you keep?

3. Hint 3: Name the pattern

   For each length, the only thing worth remembering is the smallest number that can end an increasing subsequence of that length. One best value per length, updated as each number is read, is one-dimensional dynamic programming. The values stay sorted, so a binary search finds the one to change. The signal: the longest selection that keeps its order. Read the lesson on one-dimensional dynamic programming.

4. Hint 4: State the invariant

   Keep a list of tails. A tail is the last number of an increasing subsequence. Entry k of the list, counting from 1, is the smallest tail of any increasing subsequence of k numbers among those read so far. The list is always in increasing order, and its length is the longest length found.

5. Hint 5: Sketch the pseudocode

   tails = empty list. For each number x: use binary search to find the first position where tails holds a value that is not smaller than x. If there is no such position, add x at the end. Otherwise put x at that position. Return the length of tails.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Maintain the smallest possible tail for each subsequence length. Replace the first tail at least as large as the next value.

The slow way

For each number, look back at every earlier number that is smaller, take the longest increasing subsequence that ends there, and add one. It is correct and a fine first solution, but every number looks at all the numbers before it. For 2,500 numbers that is 3,123,750 looks.

The insight

Call the last number of an increasing subsequence its tail. Of all the increasing subsequences of one length, only the one with the smallest tail matters: any number that can extend another of them can extend that one too. So one tail per length is enough to remember. Those tails are in increasing order, which lets a binary search find where a new number belongs.

Step by step

1. Start an empty list of tails: one smallest last number per length. A tail is the last number of an increasing subsequence. Position k of the list, counting from 1, will hold the smallest tail of any increasing subsequence of k numbers among those read so far.
2. For each number, find the first tail that is not smaller than it. Every tail before that position is smaller than the number, so the number can follow those subsequences. The list is in increasing order, so a binary search finds the position by halving the range each time.
3. No such tail: the number is larger than all, so add it at the end. With an empty list the number starts length 1. Otherwise it is larger than the last tail, so it can follow a subsequence of the longest length so far and make one that is one number longer.
4. Otherwise replace that tail with the number, which is no larger. The number can end an increasing subsequence of this length, and it is no larger than the old tail. A lower tail is easier for later numbers to extend.
5. Return the number of tails: the longest length reached. There is one tail for each length that some increasing subsequence has reached, so the number of tails is the longest length. The tails themselves need not be an answer: 3, 4, -1 gives -1, 4, though -1 comes last.

The same numbered steps are the comments in each solution.

function solve(nums) {
  // 1. Start an empty list of tails: one smallest last number per length
  const tails = [];
  // 2. For each number, find the first tail that is not smaller than it
  for (const n of nums) {
    // The tails are in increasing order, so one look at the middle tail
    // rules out half of the positions that are left.
    let l = 0,
      r = tails.length;
    while (l < r) {
      const m = (l + r) >>> 1;
      if (tails[m] < n) l = m + 1;
      else r = m;
    }
    // 3. No such tail: the number is larger than all, so add it at the end
    if (l === tails.length) tails.push(n);
    // 4. Otherwise replace that tail with the number, which is no larger
    else tails[l] = n;
  }
  // 5. Return the number of tails: the longest length reached
  return tails.length;
}

function solve(nums: number[]): number {
  // 1. Start an empty list of tails: one smallest last number per length
  const tails: number[] = [];
  // 2. For each number, find the first tail that is not smaller than it
  for (const n of nums) {
    // The tails are in increasing order, so one look at the middle tail
    // rules out half of the positions that are left.
    let l = 0,
      r = tails.length;
    while (l < r) {
      const m = (l + r) >>> 1;
      if (tails[m] < n) l = m + 1;
      else r = m;
    }
    // 3. No such tail: the number is larger than all, so add it at the end
    if (l === tails.length) tails.push(n);
    // 4. Otherwise replace that tail with the number, which is no larger
    else tails[l] = n;
  }
  // 5. Return the number of tails: the longest length reached
  return tails.length;
}

def solve(nums):
    # 1. Start an empty list of tails: one smallest last number per length
    tails = []
    # 2. For each number, find the first tail that is not smaller than it
    for num in nums:
        # The tails are in increasing order, so one look at the middle tail
        # rules out half of the positions that are left.
        left, right = 0, len(tails)
        while left < right:
            mid = (left + right) // 2
            if tails[mid] < num:
                left = mid + 1
            else:
                right = mid
        # 3. No such tail: the number is larger than all, so add it at the end
        if left == len(tails):
            tails.append(num)
        # 4. Otherwise replace that tail with the number, which is no larger
        else:
            tails[left] = num
    # 5. Return the number of tails: the longest length reached
    return len(tails)

Example 2, traced

Input
nums = [0,1,0,3,2,3]

Output
4

Why it works

Position k of the list always holds the smallest tail of any increasing subsequence of k numbers among those read so far. A new number either extends the longest subsequence, or gives one length a tail that is no larger, and it changes nothing else. So when every number has been read, the number of tails is the longest length that exists.

Time and space

Time O(n log n), extra space O(n). Each of the n numbers does one binary search over at most n tails. A binary search halves its range every round, so it needs about log n looks, which gives O(n log n) time. The list holds at most n tails, so the space is O(n).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Searching for the first tail that is larger than the number, not the first that is not smaller. A number equal to the last tail is then added at the end, and 7, 7, 7 gives 3 instead of 1.
• Skipping a number that cannot go at the end. For 0, 1, 0, 3, 2, 3 that answers 3 instead of 4: the 2 has to replace the first 3 so that the last 3 can be added.
• Ending the search range at the last tail and not one place past it. Then a number larger than every tail has no place of its own and overwrites the last tail: 0, 1, 0, 3, 2, 3 gives 1.

Pattern

One-dimensional dynamic programming. Builds on Binary Search and Koko Eating Bananas.

Keep going