LIS in n log n with patience piles

Why this matters

The grid paths, LCS and LIS lesson showed how to find the longest increasing subsequence with a table. That method compares each element with every element before it, so it takes about n times n divided by 2 steps. For 10 elements that is about 50 steps, which is nothing. For 200,000 elements it is about 20 billion steps, which is far too slow for a program that must answer in a second.

This lesson gets the answer in about n times log n steps. For 200,000 elements, log n is about 18, so the work is roughly 3.6 million steps. The method keeps a small sorted list, and for each new number it uses binary search to find where that number goes in the list. Binary search is a way to find a value in a sorted list by checking the middle, then throwing away the half that cannot contain it. Each check halves the range, so a list of a million items needs about 20 checks.

The method is also a good example of a table whose cells mean something different from what you first expect. The list it builds is not the answer itself. It is a summary that gives the right length, and the lesson shows how to turn that summary into one real sequence.

The problem

A subsequence is a list you get by keeping some elements of a sequence and dropping the others. The order of the kept elements stays the same. An increasing subsequence has each element larger than the one before it. The longest increasing subsequence, called the LIS for short, is the one with the most elements.

Take this sequence of eight numbers:

10 9 2 5 3 7 101 18

Some increasing subsequences are 10 101, 2 5 7 and 9 18. The longest has four elements, and one example is 2 3 7 18. Another length-4 answer is 2 5 7 101. Both are correct, so the answer is not always one unique list. The length is always 4.

This lesson uses a strictly increasing rule. Each element must be larger than the one before, so two equal numbers cannot both be in the list. Later the mistakes section shows what changes if equal numbers are allowed.

The idea: the smallest tail for each length

The key idea is a list called tail. Its entry at position k is the smallest possible last value of an increasing subsequence of length k + 1, among the numbers read so far. Position 0 holds the smallest last value of any length-1 subsequence, which is just the smallest number seen. Position 1 holds the smallest last value of any length-2 subsequence, and so on.

Keeping the smallest last value is the point. A subsequence that ends with a small number has more room for numbers that come later. If two subsequences have the same length, the one that ends lower can be extended by more future numbers.

The name "patience piles" comes from a card game called patience, which is also known as solitaire. You deal cards one at a time into piles. A card goes onto the leftmost pile whose top card is greater than or equal to it, which replaces that top card. If no pile has a top that large, a new pile starts on the right. The top card of each pile plays the role of one entry in tail. The number of piles at the end is the LIS length. The piles are only a picture to help remember the rule. The program stores numbers, not piles.

Trace the list by hand

Read the eight numbers one at a time, and keep the tail list up to date.

• Read 10. The list is empty, so 10 starts the list. The list is 10.
• Read 9. Position 0 holds 10, which is not less than 9. So 9 replaces 10, because a length-1 subsequence ending in 9 is better than one ending in 10. The list is 9.
• Read 2. Position 0 holds 9, which is not less than 2. So 2 replaces 9. The list is 2.
• Read 5. Position 0 holds 2, which is less than 5. So 5 is larger than every entry, and it starts a new length-2 entry. The list is 2 5.
• Read 3. Position 0 holds 2, which is less than 3. Position 1 holds 5, which is not less than 3. So 3 replaces 5. The list is 2 3. A length-2 subsequence now ends in 3, which is better than ending in 5.
• Read 7. It is larger than every entry, so it extends the list. The list is 2 3 7.
• Read 101. It extends the list again. The list is 2 3 7 101.
• Read 18. Position 3 holds 101, which is not less than 18. So 18 replaces 101. The list is 2 3 7 18.

The final list has four entries, so the LIS length is 4. The list 2 3 7 18 is a real increasing subsequence of the input, but it is not always the case that the list itself is a real subsequence, as the mistakes section shows.

The program below prints the list after each number. The input is the same eight numbers.

Output:

read 10 -> tail = 10
read 9 -> tail = 9
read 2 -> tail = 2
read 5 -> tail = 2 5
read 3 -> tail = 2 3
read 7 -> tail = 2 3 7
read 101 -> tail = 2 3 7 101
read 18 -> tail = 2 3 7 18

Why the list stays sorted

The tail list is always in increasing order, and that is what makes binary search possible. Here is the reason. Suppose entry k + 1 is some value t. It is the smallest last value of a subsequence of length k + 2. Remove the last element of that subsequence, and what is left is a subsequence of length k + 1 whose last value is smaller than t. Entry k is the smallest last value of any length k + 1 subsequence, so entry k is at most that smaller value. So entry k is less than entry k + 1.

Because the list is sorted, binary search can find the first entry that is not less than the new number. Call it the place for x. Every entry before the place is less than x, and the place itself holds a value that is at least x.

Step 1: the binary search

The C++ standard library has a function for this. lower_bound takes a range that is sorted and a value, and it returns an iterator to the first element that is not less than the value. An iterator is a position marker that points into the container. If every element is less than the value, it returns the end position, which is one past the last element.

The two cases map to the two possible actions:

• If lower_bound returns the end position, the new number is larger than every entry, so the list grows by one.
• Otherwise, the new number replaces the entry at that position. The entry becomes smaller or stays the same, so future numbers have an easier time extending it.

This is the whole algorithm. The loop reads each number, runs one binary search, and does one push or one replacement. The list length at the end is the answer.

The length-only program

Here is the complete program that prints only the LIS length. It reads a count, then that many numbers.

Type 8 in the Input box, press Enter, then type 10 9 2 5 3 7 101 18 on one line, and press Run.

Output:

LIS length = 4

The time is n log n. The loop runs once per number, and each lower_bound takes about log n steps. The space is O(n) (memory that grows with n) in the worst case, because the list can hold every number, for example when the input is already sorted.

Step 2: rebuilding one real sequence

The length is the first thing a user asks for, but a question like "which numbers form the longest increasing subsequence?" needs the numbers. The tail list cannot give them back directly. Its entries are the smallest last values for each length, and those entries were overwritten many times.

The fix is to store links while the program runs. The tail list holds values only, and it does not say which input element each value came from. Keep two more lists:

• tailIdx[k] holds the index in the input of the element stored at tail[k]. This tells you which input element is the current tail.
• prev[i] holds the index of the element that comes just before input element i in a longest run that ends at i.

When a new number a[i] goes into position k, the element just before it in the run must be the current tail for length k, which is tailIdx[k - 1]. That is the element at position k - 1, because the run for length k ends at position k - 1. So prev[i] is set to tailIdx[k - 1]. If k is 0, the new number starts a run, and there is no element before it, so prev[i] is -1.

At the end, start at the index stored in tailIdx for the last position, and follow prev back to the start. Then reverse the list.

Here is the full program.

Type 8 in the Input box, press Enter, then type 10 9 2 5 3 7 101 18 on one line, and press Run.

Output:

LIS length = 4
one LIS: 2 3 7 18

Walk through the links for this input. The last tail is 18, at index 7. Its prev is index 5, which holds 7. The prev of 7 is index 4, which holds 3. The prev of 3 is index 2, which holds 2. The prev of 2 is -1, so the walk stops. Reversed, that is 2 3 7 18.

Why the links stay correct

A prev link is set once, when its element is read, and it is never changed. At that moment tailIdx[k - 1] is an element that came earlier in the input and has a smaller value than a[i], because lower_bound placed a[i] after it. Later numbers can replace entries in tail or tailIdx, but they cannot change the element that a stored link points to. So the chain of links from the end always gives a real run of the input, with the same length as the tail list.

Why the tail list is not the answer

It is tempting to print tail as the answer. That is wrong in general. Take the input 1 2 0. Read 1, and the list is 1. Read 2, and the list is 1 2. Read 0, which replaces position 0, and the list becomes 0 2. The length is 2, which is correct, but 0 2 is not a subsequence of 1 2 0, because 0 comes after 2 in the input. The real longest increasing subsequence is 1 2. The link method prints it, as the mistakes section shows.

A second example with a longer answer

The third example has more numbers and a longer answer, so the links are used more. Take this input of twelve numbers:

3 1 4 1 5 9 2 6 5 3 5 8

The program below runs the link method on this input and prints the length and one answer.

Type 12 in the Input box, press Enter, then type 3 1 4 1 5 9 2 6 5 3 5 8 on one line, and press Run.

Output:

LIS length = 5
one LIS: 1 2 3 5 8

Check the answer by reading the input and counting from 1. The numbers 1, 2, 3, 5 and 8 appear in that order: the 4th number is 1, the 7th is 2, the 10th is 3, the 11th is 5, and the 12th is 8. The 1 is the 4th number, not the 2nd, because the 4th number replaced the 1 that the 2nd number had put in the tail list. The 2nd number would also give a valid answer, 1 2 3 5 8, so the links return one of several correct answers.

Here the final tail list is 1 2 3 5 8, which is also a real subsequence. That happened to be true for this input. The 1 2 0 example above shows it is not always true.

Common mistakes

Using the wrong bound for equal numbers

The lesson uses lower_bound, which finds the first entry that is not less than the new number. That makes the rule strict, so an equal number replaces an entry and does not extend the list. If you want equal numbers to count, as in a non-decreasing sequence, use upper_bound instead. Here is a program that runs both versions on the input 2 2 2.

Output:

strict (lower_bound) length = 1
non-strict (upper_bound) length = 3

If the question says "increasing" and you use upper_bound, you count 2 2 2 as an increasing run of length 3, which is wrong. Read the question's wording closely, and check it with a small input that has repeated values.

Assigning the iterator to an int

lower_bound returns an iterator, not a position number. A common slip is to store the result directly in an int. The compiler rejects it, and the message shows the type that was returned.

#include <algorithm>
#include <vector>
using namespace std;
 
int main() {
    vector<int> tail = {2, 3, 7};
    int k = lower_bound(tail.begin(), tail.end(), 5);
    return k;
}

The g++ 15 compiler prints:

lis4.cpp: In function ‘int main()’:
lis4.cpp:7:24: error: cannot convert ‘__gnu_cxx::__normal_iterator<int*, std::vector<int> >’ to ‘int’ in initialization

The fix is to subtract the start of the range, as the programs above do: int k = lower_bound(tail.begin(), tail.end(), x) - tail.begin();. The subtraction gives the position as a number.

Reading the last entry of an empty list

If no number has been read, tail is empty. Asking for tailIdx.back() then reads a position that does not exist. The program below does that with an empty list.

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector<int> tailIdx;
    int last = tailIdx.back();  // no element was added yet
    cout << last << "\n";
}

With the Ubuntu g++ 15 used to test this lesson, compiling and running it stops with this message:

/usr/include/c++/15/bits/stl_vector.h:1370: constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::back() [with _Tp = int; _Alloc = std::allocator<int>; reference = int&]: Assertion '!this->empty()' failed.

The fix is the early return in the link program: if (tail.empty()) return 0;. Check the empty case on purpose, because the input 0 is valid.

Reading the previous entry when there is none

When the new number goes into position 0, there is no earlier tail. The line prev[i] = tailIdx[k - 1] would then read index -1. Write it as k > 0 ? tailIdx[k - 1] : -1, as the program does. Without that check, the program reads an index that does not exist. This example reads index -1 on purpose to show the message:

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector<int> tailIdx = {0};
    int k = 0;  // first element of a run, so there is no earlier tail
    cout << "tailIdx[k - 1] = " << tailIdx[k - 1] << "\n";
}

The program stops with this message:

/usr/include/c++/15/bits/stl_vector.h:1263: constexpr std::vector<_Tp, _Alloc>::reference std::vector<_Tp, _Alloc>::operator[](size_type) [with _Tp = int; _Alloc = std::allocator<int>; reference = int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.

The index -1 becomes a very large unsigned number, which is outside the vector. The check k > 0 prevents it.

Printing the tail as the answer

As shown in the section on why the tail is not the answer, printing tail gives 0 2 for the input 1 2 0, which is not a subsequence of the input. Print the list that the links rebuild instead.

Practice

Each exercise has an answer below it. Try the exercise before you read the answer.

Exercise 1

Change the program so equal numbers may both appear in the answer, which means a non-decreasing subsequence. What is the length for the input 1 3 3 2 4?

Show the answer

Use upper_bound in place of lower_bound. The length is 4, from the subsequence 1 3 3 4. With lower_bound the length would be 3, from 1 3 4.

Exercise 2

Run the length-only program on the input 3 1 4 1 5 9 2 6. What is the final tail list?

Show the answer

The final list is 1 2 5 6. After reading 3, the list is 3. After 1, it is 1. After 4, it is 1 4. The second 1 leaves it as 1 4. After 5, it is 1 4 5, and after 9 it is 1 4 5 9. Reading 2 gives 1 2 5 9, and reading 6 gives 1 2 5 6. The length is 4.

Exercise 3

Find the length of the longest decreasing subsequence of 10 9 2 5 3 7 101 18. A decreasing subsequence has each element smaller than the one before it.

Show the answer

The length is 4. One answer is 10 9 5 3. A simple way to solve it is to multiply every number by -1, so a decreasing run becomes an increasing run, and then run the length-only program. Each negated value is taken in the same order, so the length is the same.

Exercise 4

Why does the link method store tailIdx[k], the index of the element, and not only tail[k], the value?

Show the answer

The value alone does not say where the element is in the input, so you cannot follow prev links with it. Two different input elements can have the same value, and the links must point to the exact element. The index also lets you check that the chain goes backwards through the input.

Exercise 5

In the link program, the line prev[i] = k > 0 ? tailIdx[k - 1] : -1; is changed to prev[i] = tailIdx[k - 1];. Which input causes a problem, and what goes wrong?

Show the answer

Any number that goes to position 0 causes the problem, and the first number always does. For the input 5, the first number goes to position 0, so k is 0, and tailIdx[-1] is read. That index does not exist, and the program stops with the assertion message shown in the mistakes section. The fix is the check k > 0.

Summary

• The longest increasing subsequence can be found in n log n time by keeping the smallest last value for each length in a sorted list.
• Binary search with lower_bound finds the spot for each new number, which either grows the list or replaces one entry.
• The list length is the answer, but the list itself is not always a real subsequence, so it should not be printed.
• Store the index of each tail and a prev link for each element, so you can walk back and rebuild one valid answer.
• Choose lower_bound for strictly increasing answers and upper_bound for non-decreasing ones.
• Guard the empty list and the first position, because reading the last entry of an empty list or index -1 fails at run time.