LIS in n log n with bisect and patience piles

Why this matters

A longest increasing subsequence, usually called LIS, is the longest run of values that keeps rising while keeping their original order. It appears in plain problems. A list of measurements that only go up. A stack of boxes that each fit inside the next. A chain of tasks where each one can start only after the previous one has finished a bigger job. It is also a common interview question, and the fast method for it uses a binary search trick that is worth learning.

The one-dimensional DP lesson earlier in this module gives a slower method with two nested loops. This lesson keeps the same question and makes the method much faster. The fast method has a name in this lesson: patience piles, after a card game.

By the end you will be able to define a subsequence, explain why keeping the smallest last value for each length gives the answer, write the Python code that finds the length, and rebuild one actual sequence using back pointers.

Reading the code in this lesson

The code uses a few Python features. You need only these to follow it.

• A list such as [10, 9, 2] holds values in order. The first value has index 0.
• tails[k] reads or writes the value at index k. tails.append(x) adds x to the end. len(tails) is the number of values.
• from bisect import bisect_left brings in a function from the standard library, which is the set of tools that comes with Python. No install is needed.
• bisect_left(items, x) searches a sorted list items for x. It returns the position where x belongs. That position is the index of the first value that is not smaller than x, or the length of the list if every value is smaller. It does not change the list.
• bisect_left(items, x, key=f) works the same way, but compares f(item) for each item in the list. The x is not passed through f.
• enumerate(nums) gives pairs of an index and a value, such as (0, 10) and (1, 9).
• seq.reverse() flips a list in place.
• -1 is used as a marker for "no previous value". It is not a real index.

Readers who know Java: bisect_left returns the position directly. Java's Collections.binarySearch returns a negative number when the key is missing, so the Java version needs one extra step to get the position.

What a subsequence is

A subsequence keeps the order of the original list but may skip items. Take this list:

index:  0   1   2   3   4   5    6     7
value: 10   9   2   5   3   7  101    18

The values 2, 5, 7, 101 appear in this order in the list. They come from indexes 2, 3, 5 and 6. Index 4 was skipped, and so was everything else. That is a subsequence. The values 5, 2, 7 are not a subsequence, because 5 comes after 2 in the list, not before it.

The list is increasing when each value is bigger than the one before. The word strictly means equal values do not count. So 7, 7 is not strictly increasing.

For the list above, the longest strictly increasing subsequence has length 4. Several sequences reach that length: 2, 3, 7, 18; 2, 5, 7, 101; and 2, 5, 7, 18. The length is the same for all of them. The lesson shows how to get that length fast and how to produce one of the sequences.

A short check: the list 7, 7, 7 has longest strictly increasing length 1, because no value is bigger than the one before it.

The slow method and why it is too slow

The slow method, from the one-dimensional DP lesson, works like this. For each position i, look at every earlier position j. If the value at j is smaller than the value at i, the best sequence ending at i can be one longer than the best ending at j. Keep the largest result.

That takes about n * n steps for a list of n numbers. For a list of 10 numbers, that is about 100 steps, which is fine. For a list of 100,000 numbers, it is about 10 billion steps, which takes far too long.

The method in this lesson takes about n * log n steps. The term log n here means the number of times you can cut n in half before you reach 1. For 100,000 numbers, that is about 17. So the work is about 100,000 times 17, which is 1.7 million steps. That is the gain this lesson is about.

The card game

Imagine you are dealt cards one at a time from the list. The cards are numbers. You place them on piles on a table, using this rule for each new card x:

1. Look at the top card of each pile, starting from the left pile.
2. Put x on the leftmost pile whose top card is not smaller than x. The x becomes the new top card of that pile, and the old top card is covered.
3. If every pile has a top card smaller than x, start a new pile at the right end and put x on it.

At the end, count the piles. The count is the length of the LIS.

Deal the list 10, 9, 2, 5, 3, 7, 101, 18. The table below shows the top cards after each card, read from left to right.

There are four piles at the end, so the LIS length is 4.

Why the top cards are the useful part

The top cards are the smallest possible last values for each length. Here is why that matters. Suppose there is one increasing sequence of length 2 that ends in 5, and another that ends in 3. The one that ends in 3 is better. Any number bigger than 5 is also bigger than 3, so anything that can follow the sequence ending in 5 can also follow the sequence ending in 3.

So for each length, the lesson keeps only the best ending, which is the smallest last value. The top card of pile k is the smallest last value of any increasing sequence of length k.

The top cards always stay in increasing order from left to right. Here is why. When card x lands on pile p, the pile to the left of p has a top card smaller than x, because p was the leftmost pile that could take x. The pile to the right of p has a top card bigger than the old top of p, which was at least x. After the change, the top of p is x, which is smaller than the pile on its right and bigger than the pile on its left. So the order holds.

This sorted order is what makes binary search possible.

Finding the pile with binary search

The top cards form a sorted list. The leftmost pile whose top is not smaller than x is the first position where the list has a value of at least x. Finding that position in a sorted list is what binary search does.

Binary search works like this. Look at the middle entry. If it is big enough, the answer is at that entry or to its left, so search the left half. If it is too small, the answer is to the right, so search the right half. Each step halves the search range. A list of 100,000 entries needs about 17 steps.

In Python, bisect_left does this for a sorted list. It returns the position where x belongs. If x is already in the list, it returns the position of the first matching value, so x replaces that value. If x is bigger than every value, it returns the length of the list, so x is added at the end.

Finding the length in Python

The code below keeps a list called tails. The entry tails[k] is the top card of pile k + 1, which is the smallest last value of an increasing sequence of length k + 1.

The loop reads each number x once. bisect_left finds pos, the leftmost pile that can take x. If pos is the end of the list, every pile is too small, so the code adds a new pile. Otherwise it replaces the top card of pile pos with x.

Save the file as lis_length.py and run it with python3 lis_length.py. The output is:

after 10: [10]
after 9: [9]
after 2: [2]
after 5: [2, 5]
after 3: [2, 3]
after 7: [2, 3, 7]
after 101: [2, 3, 7, 101]
after 18: [2, 3, 7, 18]
LIS length = 4

Each line matches a row of the card table. The last line is the answer.

Rebuilding one valid sequence

The length tells you how long the answer is, but not which values form it. The list tails holds the best last values, and that is not always a real sequence from the input. The mistakes section shows why.

To rebuild a sequence, store a back pointer for every number. A back pointer is the index of the number that comes before it in its sequence. Here is the rule. When number i lands on pile p, its back pointer is the index of the top card of pile p - 1 at that moment. If p is the first pile, the back pointer is -1, which means "no previous number".

Why is this valid? The top card of pile p - 1 is smaller than i's value, because that pile was the one to the left. It also sits earlier in the list, so its index is smaller. Following back pointers therefore gives a chain of indexes that goes forward in the list and rises in value.

To rebuild the answer, start at the index on top of the last pile. Follow the back pointers until you reach -1. The values you pass are the sequence, but they come out in reverse order, so the code reverses the list at the end.

The list tail_index holds indexes, not values. The key argument tells bisect_left to compare the value at each stored index, nums[j], with the new number. The new number is passed as a value, not an index.

Save the file as reconstruct.py and run it. The output is:

input:   [10, 9, 2, 5, 3, 7, 101, 18]
one LIS: [2, 3, 7, 18]
prev:    [-1, -1, -1, 2, 2, 4, 5, 5]
input:   [0, 1, 0, 3, 2, 3]
one LIS: [0, 1, 2, 3]
input:   [6, 1, 8, 2, 9, 3, 5, 4, 10, 7, 11, 12]
one LIS: [1, 2, 3, 4, 7, 11, 12]
prev:    [-1, -1, 1, 1, 3, 3, 5, 5, 7, 7, 9, 10]

Read the first prev line with the input. Index 7 holds the value 18, and its back pointer is 5, which holds the value 7. Index 5 has back pointer 4, which holds 3. Index 4 has back pointer 2, which holds 2. Index 2 has back pointer -1, so the walk stops. Reading the values in order gives 2, 3, 7, 18.

The code stores the indexes in tail_index, not the values. When the search needs a value, key reads nums at that index.

Example two: duplicates

This example has a repeated value. The list is 4, 10, 4, 3, 8, 9.

Run the same card game. The first card 4 starts a pile. The card 10 goes on a new pile, so the tops are 4, 10. The second 4 lands on the first pile, which has top 4. The top 4 is not smaller than 4, so it is replaced by the same 4. The tops stay 4, 10. The card 3 goes on the first pile, so the tops are 3, 10. The card 8 is smaller than 10, so it goes on the second pile, giving 3, 8. The card 9 starts a new pile, giving 3, 8, 9.

The lis_length function from the previous section prints:

after 4: [4]
after 10: [4, 10]
after 4: [4, 10]
after 3: [3, 10]
after 8: [3, 8]
after 9: [3, 8, 9]
LIS length = 3

The length is 3, and the sequence is 3, 8, 9. The repeated 4 changed nothing, because a value equal to a top card does not extend a strictly increasing sequence.

Example three: a longer list with back pointers

The list in the reconstruct program has 12 numbers: 6, 1, 8, 2, 9, 3, 5, 4, 10, 7, 11, 12. The program gives the length 7, with the sequence 1, 2, 3, 4, 7, 11, 12. The back pointers are the useful part to check by hand.

The prev list printed for this list is:

[-1, -1, 1, 1, 3, 3, 5, 5, 7, 7, 9, 10]

Start at index 11, which holds 12. Its back pointer is 10, which holds 11. Index 10 points to index 9, which holds 7. Index 9 points to index 7, which holds 4. Index 7 points to index 5, which holds 3. Index 5 points to index 3, which holds 2. Index 3 points to index 1, which holds 1. Index 1 points to -1, so the walk stops. The values, read in order, are 1, 2, 3, 4, 7, 11, 12.

Another valid answer may exist, because a list can contain more than one sequence of the same length. The program gives one of them.

Common mistakes

Allowing equal values

A common mistake is to treat an equal value like a bigger one. The code below has the correct method and a wrong one, so you can compare them.

The output is:

strictly increasing: 1
wrong equal handling: 3

The correct answer is 1. The wrong version uses bisect_right. That function returns the position after any equal values, so each 7 is added after the previous one. The list becomes [7, 7, 7], and the answer counts equal values as increasing. The fix is bisect_left, which returns the position of the first equal value, so the equal value replaces it.

Using is instead of ==

Python has two ways to compare. == asks whether two values are equal. is asks whether two names point to the same object. Two equal numbers are not always the same object. The next program shows the difference:

The output is:

True False
True False
True False

The first line shows that a and b hold equal values, but they are different objects, so is gives False. The second line shows 256 and 257 behaving differently. In CPython, the standard Python program, small integers from -5 to 256 are shared, so is can give True for them. Other numbers are created fresh each time, so is gives False even when the values match. Results of is for numbers can therefore change with the value, which makes this a silent bug. Use == to compare numbers, and keep is for checking None.

Writing past the end of the list

When pos equals the length of the list, every pile is too small, and the code must add a new pile with append. If you assign to tails[pos] at that position, Python stops with an error. The command python3 -c "small = [1, 2, 3, 4]; small[4] = 9" does that on purpose, with a list of four values and an index of 4, which does not exist. The output is:

Traceback (most recent call last):
  File "<string>", line 1, in <module>
    small = [1, 2, 3, 4]; small[4] = 9
                          ~~~~~^^^
IndexError: list assignment index out of range

The last line says what went wrong: the assignment used an index that is outside the list. The caret line under the code points at the index. The fix is the if pos == len(tails) branch in the LIS code, which calls append instead of assigning.

Returning the list as the answer

The tails list is not a sequence from the input. The next example shows this. The list is 2, 3, 1. The lis_length function from the previous section prints:

after 2: [2]
after 3: [2, 3]
after 1: [1, 3]
LIS length = 2

The final tails list is [1, 3]. But in the input, 1 comes after 3, so 1 then 3 is not a subsequence. The length 2 is still correct, because the real answer is 2, 3. The lesson is that the list gives the length, and the back pointers give a real sequence. Never return tails itself as the answer.

Practice

Exercise 1. Trace the tails list for the input 3, 4, -1, 0, 6, 2, 3. What is the final list, and what is the LIS length?

Show the answer

The list after each card is [3], then [3, 4], then [-1, 4], then [-1, 0], then [-1, 0, 6], then [-1, 0, 2], then [-1, 0, 2, 3]. The final list is [-1, 0, 2, 3], and the LIS length is 4. The longest_increasing function returns the sequence [-1, 0, 2, 3] for this input, which has length 4.

Exercise 2. The input is 7, 7, 7. The method in this lesson gives 1. What would the answer be if equal values were allowed to extend a sequence?

Show the answer

It would be 3, because 7, 7, 7 is non-decreasing, which means each value is at least as big as the one before. The wrong version in the mistakes section, which uses bisect_right, prints 3. The strict version used in this lesson, which uses bisect_left, gives 1.

Exercise 3. Rebuild one longest increasing subsequence for the input 0, 1, 0, 3, 2, 3. Give the values and the indexes they come from.

Show the answer

The sequence is 0, 1, 2, 3. The indexes are 0, 1, 4 and 5. The program prints [0, 1, 2, 3], which matches. The 0 at index 2 is not used, because no 1 comes after it.

Exercise 4. The input is 2, 3, 1. Give one real increasing subsequence of length 2, and explain why the final tails list is not a valid answer.

Show the answer

One real subsequence is 2, 3, from indexes 0 and 1. The final tails list is [1, 3]. It is not a valid answer, because in the input, 1 is the last value, so 1 cannot come before 3 in a subsequence. The list only records the smallest last value for each length, and those values do not have to come from one sequence.

Exercise 5. Find the length of the LIS for 4, 10, 4, 3, 8, 9, and give one sequence of that length.

Show the answer

The length is 3. One sequence is 3, 8, 9, from indexes 3, 4 and 5. Another is 4, 8, 9, from indexes 0, 4 and 5. The longest_increasing function returns 3, 8, 9 for this input.

Summary

• A subsequence keeps the original order and may skip items. An increasing one has each value bigger than the one before.
• The fast method keeps the smallest last value for each length. Those values form a sorted list, so bisect_left can find where a new value goes.
• The list size is the LIS length, but the list itself is not always a real sequence.
• Back pointers record which earlier item each item extends, so following them rebuilds one valid sequence.
• Use bisect_left for strictly increasing answers, and use == rather than is when comparing numbers.