Grid paths, LCS and LIS

Why it matters

Two-dimensional DP appears whenever a problem has two positions that change at the same time. The positions might be a row and a column in a map, or a letter in one string and a letter in another. Many real tools work this way. A spell checker compares two words. A version control tool compares two versions of a file. A route planner counts paths on a grid. The three problems in this lesson are standard interview questions, and each one builds on the one-dimensional tables you met in the last two lessons.

By the end of this lesson you will be able to draw a two-dimensional table, fill it in the right order, read off the answer, and explain the complexity. You will also meet a clever way to solve the third problem in far less time than the obvious method, which interviewers like to ask about.

Part 1: from one dimension to two

In the last lesson a table had one index, such as dp[i]. Here a table has two indexes, dp[r][c], which means a row and a column. You can picture it as a grid of boxes, one box for each pair of indexes. The first index picks the row, and the second picks the column, the same way you read a chessboard or a spreadsheet.

In C++ a two-dimensional table is a vector of vectors:

vector<vector<int>> dp(rows, vector<int>(cols, 0));

This line makes rows inner vectors, each with cols zeros. You can then write dp[r][c] anywhere in the table. Each inner vector is a separate row of numbers, and the outer vector holds the rows. The memory cost is one number per cell, plus a small overhead for each row.

Two-dimensional DP keeps the same five-step recipe from the earlier lessons. Define what dp[r][c] means in a plain sentence. Set the base cases along the edges. Write the recurrence for a cell from its neighbours. Choose a loop order that fills the neighbours first. Read the answer from the right cell.

The loop order is the new thing to think about. With two indexes you usually use two nested loops. The outer loop walks the rows from top to bottom, and the inner loop walks the columns from left to right. That order guarantees that the cell above and the cell to the left are already filled, so both are ready when a cell needs them. If a recurrence reads the cell below or to the right, the loops must go the other way. Always check which neighbours the recurrence reads before you choose the loops.

Worked example: grid paths with walls

A robot starts in the top-left corner of a grid. It wants to reach the bottom-right corner. Each move is one step right or one step down. Some cells contain a wall, which the robot cannot enter. How many different paths avoid the walls?

Picture a small city map. Streets run east and west, and avenues run north and south. The robot can only walk east or south, so it never turns back. Some blocks are closed for construction. The question is how many routes from the start to the destination do not pass through a closed block.

Let dp[r][c] be the number of paths from the start to cell (r, c). Here (r, c) means row r and column c, with rows and columns counted from zero. If the cell is a wall, dp[r][c] is 0, because no path can enter it.

Now think about how the robot can arrive at a free cell. It must come either from the cell above, which is (r - 1, c), or from the cell to its left, which is (r, c - 1). Those are the only two ways in. So the number of paths is the sum of the two counts, where a missing neighbour (off the grid) contributes nothing:

dp[r][c] = dp[r - 1][c] + dp[r][c - 1]

The base case is the start cell, dp[0][0] = 1, because there is exactly one way to be at the start: stand there. The first row and the first column have only one neighbour each, so the same formula handles them without any special case, as long as you treat cells off the grid as 0.

Here is the 3 by 3 grid with a wall in the middle, and the counts that the recurrence produces.

Table of path counts for a 3 by 3 grid with a wall in the centre, the answer 2 highlighted in the bottom right

Trace each row. The first row has no walls, so every cell has one path: the robot walks straight right. The second row starts with a free cell that has one path from above. The centre is the wall, so its count is 0. The cell to its right has one path from above and nothing from the wall on its left, so its count is 1. The third row starts with one path. The cell after it has a wall above it, so its only path comes from the left. The bottom-right cell has the cell above (count 1) and the cell to its left (count 1), so the answer is 2.

The two paths are the two ways around the wall: right, right, down, down, and down, down, right, right. Check your table against this list, and you have found a useful habit. A DP table is a compact summary of many paths, and you can always check it by listing a few.

The Viz below steps through the same table one cell at a time, so you can watch the counts build up from the start cell. Each new cell reads the cell above and the cell to its left.

The program

Here is the complete program. The input gives the number of rows and columns, then one line per row. A . is a free cell and a # is a wall. The top-left and bottom-right cells are always free.

Type 3 3 in the Input box, press Enter, then type the three rows ..., .#. and ... on separate lines, and press Run.

Output:

number of paths = 2

The walls are handled by a single line: continue skips the cell, which leaves it at 0. The top row and left column need no special code, because the if (r > 0) and if (c > 0) checks drop the missing neighbours. The loops go row by row, so the cell above and the cell to the left are always filled first.

Complexity. The program visits each cell once and does constant work per cell. The time is O(rows times cols), and the table uses the same amount of space.

The answer can be huge. A grid of 60 by 60 has more paths than a 64-bit integer can hold. The usual fix, when the problem asks for it, is to take the sum modulo a fixed prime such as 1000000007 at each step. The problem set for this module uses that rule. The change is one line, dp[r][c] %= MOD, after the additions.

Part 2: the longest common subsequence

The second problem compares two strings. It asks for the length of the longest sequence of letters that appears in both strings, in the same order. The letters do not have to sit next to each other. This is the longest common subsequence, usually written LCS. It is the basis of diff tools, which show what changed between two versions of a file.

The words subsequence and substring are easy to confuse, so pin them down first. A substring is a block of consecutive letters, with nothing skipped. In ABCDE, the substring BCD is valid, but BD is not, because the letters C and D sit between them. A subsequence keeps the order but may skip letters. ACE is a subsequence of ABCDE, because you can take A, skip B, take C, skip D and take E. Every substring is a subsequence, but not every subsequence is a substring.

Take ABCBDAB and BDCABA. The sequence BCBA appears in both, in order: in the first string you take B, C, B, A with gaps, and in the second you take B, C, B, A with gaps too. No common subsequence is longer than 4, so the LCS length is 4.

The recurrence

Let dp[i][j] be the LCS length of the first i letters of string a and the first j letters of string b. The table has n + 1 rows and m + 1 columns, where n and m are the string lengths. The extra row and column are for the empty prefix. The empty prefix has no letters, so its LCS with anything is 0, and those cells are the base cases.

Now the recurrence. Look at the last letter of each prefix, a[i - 1] and b[j - 1]. There are two cases.

If the two letters match, the best answer uses that matching letter. It is one more than the LCS of the two shorter prefixes, so dp[i][j] = dp[i - 1][j - 1] + 1. Using a matching pair is never worse than leaving it out, so this choice is safe.

If the letters differ, they cannot both be used as the last letter of the match. So the answer is the better of dropping the last letter of a or dropping the last letter of b: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]).

Write the rule in plain words: "if the last letters match, extend the match; otherwise keep the better of the two shorter comparisons". That sentence is the whole method.

The index shift deserves a note. The table is one bigger than the strings, so dp[i][j] covers the first i letters, which are a[0] through a[i - 1]. The letter that dp[i][j] looks at is a[i - 1], not a[i]. Mixing these up is the most common error in this problem, and the code comments should make the shift obvious.

The table

The next diagram shows the full LCS table for ABCBDAB and BDCABA. Rows are the letters of the first string, and columns are the letters of the second. The dash marks the empty prefix. The highlighted cell, bottom right, is the answer.

LCS table for ABCBDAB against BDCABA, with rows and columns labelled by letters and the bottom right cell highlighted as 4

Look at a few cells to check the rule. Cell (1, 1) compares A with B. They do not match, so the value is the maximum of the cell above (empty prefix against B, which is 0) and the cell to the left (0), giving 0. Cell (2, 2) compares AB with BD. The last letters are B and D, which differ, so the value is the larger of the cell above (A against BD, 0) and the cell to the left (AB against B, 1). The value is 1. Cell (3, 3) compares ABC with BDC. The last letters are C and C, which match, so the value is the diagonal cell (AB against BD, 1) plus 1, which gives 2.

The Viz below steps through the LCS table. Watch for the diagonal moves, which happen only when the two letters match. Those are the cells where the answer grows.

The program

Here is the complete LCS program. It reads two lines, one string per line, and prints the length.

Type ABCBDAB in the Input box, press Enter, type BDCABA on the next line, and press Run.

Output:

LCS length = 4

The loops go row by row, so the cell above, the cell to the left and the diagonal cell are all filled first. The code reads a[i - 1] and b[j - 1] for the letters that cell dp[i][j] is about.

Complexity. Time is O(n times m), because the table has that many cells and each cell does constant work. Space is also O(n times m) for this version. The last section of this lesson shows how the space can drop to O(m).

Recovering the letters

The program prints only the length. Interviewers often ask for the string itself. To get it, walk back from dp[n][m]. If a[i - 1] equals b[j - 1], that letter is part of the answer, so move diagonally up and left. Otherwise move to whichever neighbour holds the larger value, the cell above or the cell to the left. Collect the letters as you go and reverse the list at the end. The path you walk is the same kind of trace you did for the house robber in the last lesson.

Part 3: the longest increasing subsequence

The third problem is about one list of numbers. Find the length of the longest subsequence whose values strictly increase. A subsequence keeps the order of the list but may skip items. So in 10 9 2 5 3 7 101 18, the values 2 5 7 101 form an increasing subsequence of length 4, and so do 2 3 7 18. No increasing subsequence has length 5, so the answer is 4.

"Strictly" means equal values do not count as increasing. The list 1 1 1 has an increasing subsequence of length 1, not 3. A non-strict version allows equal neighbours, and we return to that difference in the practice list.

The O(n squared) method

Let dp[i] be the length of the longest increasing subsequence that ends at position i. Ending at i is what makes the recurrence work. To extend a subsequence that ends at i, look at every earlier position j with a[j] < a[i]. Any such j can come just before i, so the candidate is dp[j] + 1. If no earlier value is smaller, the subsequence is just a[i] by itself, with length 1. So:

dp[i] = max over all j < i with a[j] < a[i] of (dp[j] + 1), or 1 if there is none

The answer is the largest dp[i], not dp[n - 1]. The longest subsequence may end anywhere in the list, and the last element is not special.

Take the example 10 9 2 5 3 7 101 18. The table of dp values is 1, 1, 1, 2, 2, 3, 4, 4. Position 0 (value 10) and position 1 (value 9) have nothing smaller before them, so each is 1. Value 2 is also 1. Value 5 extends the 2, so it is 2. Value 3 also extends the 2, so it is 2. Value 7 extends the best of 2, 5 and 3, which is a length 2 ending at 5 or 3, so 7 gets 3. Value 101 extends 7 and gets 4. Value 18 extends the length 3 ending at 7, giving 4. The largest value in the table is 4.

Here is a program for this method. It reads the number of values and then the values.

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

Output:

LIS length = 4

The table starts with every cell at 1, because each value by itself is an increasing subsequence of length 1. That is the base case, and the loop only raises a cell when it finds a longer chain. The answer is the largest cell, tracked in best.

Complexity. The inner loop runs about i times for each i, so the total is about n squared / 2. That is O(n squared) time and O(n) space. For a list of 10,000 values that is about 50 million comparisons, which is fast enough, but for a list of a million values it is far too slow. The next method is much faster.

The O(n log n) method

The faster method has a clever idea, and it is a favourite interview follow-up. Instead of storing the length for each position, keep one array tails. The entry tails[k] holds the smallest value that ends an increasing subsequence of length k + 1. The array is always sorted increasingly, because a smaller tail for a length is always better for extending later.

Process the values one at a time. For each value x, find the first entry in tails that is greater than or equal to x. Call its position k. Then replace that entry with x. There are two cases that this covers. If x is larger than every tail, it extends the longest chain, so you add it to the end. If x is smaller than some tail, it replaces that tail, which makes a better chain for that length, so future values have an easier time extending it.

The length of the answer is the size of tails at the end. Note that tails does not hold the actual subsequence at the end. It only tells you the length. The values in tails can differ from any single real subsequence, so do not read the array as the answer.

Trace the same list, 10 9 2 5 3 7 101 18. The table below shows tails after each value.

The final array has 4 entries, so the length is 4. The binary search is what makes this fast: finding the position in a sorted array takes O(log n) steps. Over n values the total time is O(n log n).

C++ has a standard function for the search. lower_bound finds the first position whose value is not less than x, which is exactly "greater than or equal to x". It works on a sorted range in O(log n) time. The program below uses it.

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

Output:

LIS length = 4

The program gives the same answer, in fewer steps. Note the choice of lower_bound and not upper_bound. The lower_bound function returns the first value that is at least x, so a value equal to x is replaced. That keeps the tails strictly increasing, which is what the strict problem needs. Using upper_bound would let equal values stack up, and the answer would be the non-strict length. The practice list below asks you to see this difference for yourself.

Complexity. Each value does one binary search, which costs O(log n), and possibly one insertion at the end. The total is O(n log n) time and O(n) space for tails in the worst case.

What happens inside

It is worth knowing how the memory for a two-dimensional table is laid out. vector<vector<int>> is not a single block of numbers. The outer vector holds one entry per row, and each entry is a separate vector with its own block of memory. Each row is contiguous, so reading across a row is fast. Reading down a column jumps from one row block to another, which is slower. That is why the loops in this lesson run across each row before moving down. The processor reads consecutive numbers quickly, and the loop order matches the memory order.

For the LCS table, the total memory is (n + 1) times (m + 1) integers. Two strings of 1,000 letters each need about a million integers, which is about 4 megabytes. That is fine. Strings of 100,000 letters would need about 40 gigabytes, which is not fine. For that reason, large inputs need a different method, such as keeping only two rows.

Two rows are enough for the LCS because a cell reads only the row above it and the cell to its left. Once the next row is started, the row before the previous one is never read again. So the program can keep two arrays, one for the row being built and one for the row above, and swap them after each row. This turns the space into O(m). The trick needs care with the diagonal value, which must be saved before the row it lives in is overwritten, but the idea is the same as the house robber space optimisation from the last lesson.

Common mistakes

An off-by-one with a[i] and a[i - 1]. The table index i means "the first i letters", so the letter it compares is a[i - 1]. Using a[i] reads the next letter, and the answer is wrong on some inputs and right on others, which is the worst kind of bug.

Confusing a subsequence with a substring. A substring must be contiguous. An LCS allows gaps. If you use the wrong one, your answer will be smaller than the true LCS whenever the common letters are not next to each other.

Reading the last LIS cell instead of the largest. The longest increasing subsequence may end anywhere in the list. Take the maximum over all dp[i]. Returning dp[n - 1] is correct only when the list happens to end at the best place.

Using <= when the problem wants strictly increasing. Equal values must not extend a chain. Use < in the comparison, and lower_bound in the fast method.

Forgetting that the start cell can be a wall. If the start is blocked, the answer is 0. The problem guarantees a free start, but a defensive check makes the program safe for other inputs.

Writing the walls as the wrong value. A wall must contribute 0 paths. If you forget the continue, the wall keeps a path count from the cells above and to the left, and the answer is too large.

Using string without std::. The name string lives in the std namespace, so the program needs the line using namespace std; or the full name std::string. Without either, the compiler stops. Here are the first lines of what g++ prints for a short program that forgets the line:

str.cpp: In function ‘int main()’:
str.cpp:4:5: error: ‘string’ was not declared in this scope
    4 |     string a;
      |     ^~~~~~

The message names the word the compiler does not know. The notes below it, which g++ prints in a longer form, list std::string as the likely meaning. The fix is the using namespace std; line under the includes.

Debugging walkthrough

Suppose the LCS program prints 3 for abc and acb, and you expect 2. Here is how to find the error.

First, work out the answer by hand. The common subsequences are ab and ac. abc contains a, then b, then c. In acb, ab appears as a at position 0 and b at position 2, and ac appears as a and c. There is no common subsequence of length 3, because acb is not abc in order. So the correct answer is 2.

Second, print the table. Add a line after the loops that prints dp[i][j] for each cell, with a space between values. The output will show the rows, and you can compare them with the hand trace.

Third, find the first wrong cell. Suppose cell (3, 3) reads 3, but the correct value is 2. Look at its two neighbours and the letters it compares: c and b. They do not match, so the value must be the larger of the cell above and the cell to the left. If the cell above is 2 and the cell to the left is 2, the answer must be 2. If the printed value is 3, the bug is in the branch, probably a missing else or an extra + 1.

Fourth, test with the tiny cases. Try ab and ba, whose LCS is 1, and aaa and aa, whose LCS is 2. Small inputs show whether the recurrence and the index shift are right before you test large ones.

Variations and edge cases

Test the following inputs before you trust a solution.

• Empty strings for LCS. The answer is 0, and the table is one cell. The loops do not run.
• Two identical strings. The LCS is the length of the string.
• Two strings with no letters in common. The LCS is 0.
• A grid of one row or one column. Every free cell has exactly one path, so the answer is 1 if the way is clear and 0 if a wall blocks it.
• A grid with a wall at the end. The answer is 0, because the target cannot be entered.
• A list of values in decreasing order. The LIS is 1, because no value is larger than the one before it.
• A list with repeated values, such as 2 2 2. Strictly, the LIS is 1. Non-strictly, it is 3.

For grid paths, the variations include moves in more directions. If the robot can also move diagonally, the recurrence adds the cell up and to the left, and the counting changes. If the robot may move left or up as well, the table has cycles, and you can no longer fill it in one pass, which is a sign that a different method is needed.

Interview questions

"Why is the LCS table one bigger than the strings?" Answer: the extra row and column represent the empty prefix. Their cells are the base cases, with value 0, and they let the recurrence work for the first letter without a special case.

"What is the difference between a subsequence and a substring?" Answer: a substring is contiguous, and a subsequence keeps the order but may skip letters. Give an example, such as ACE as a subsequence of ABCDE.

"How do you speed up the LIS?" Answer: keep a sorted array of the smallest possible tail for each length, and use binary search to place each new value. The time drops from O(n squared) to O(n log n). Explain that the array is not itself the answer.

"How do you count the paths in a grid with walls?" Answer: set each wall cell to 0, set the start to 1, and let every other cell add the cell above and the cell to the left. Explain that a wall is never entered, so its count is 0 and contributes nothing to the cells after it.

"Why does the LCS loop go forwards?" Answer: the recurrence reads the cell above, the cell to the left and the diagonal. All three have smaller indexes, so they are filled by a forward loop.

Practice

1. Easy. Build the grid table for a 2 by 2 grid with no walls. Predict the number of paths, then check it. Hint: the answer is 2.

2. Easy. Find the LCS length of ABC and ACB. List the common subsequences of length 2, then check with the table. Hint: the answer is 2.

3. Easy. Find the LCS length of abc and def. Explain why the table is all zeros.

4. Medium. Find the longest non-decreasing subsequence of 1 3 3 2 4, where equal neighbours are allowed. Predict the answer before you run the program, then compare with the strict version, which gives 3.

5. Medium. Print one longest common subsequence of ABCBDAB and BDCABA, not just its length. Walk back from the bottom right cell. Any of BCBA, BDAB or BCAB is a correct answer.

6. Medium. A grid has a wall in the start cell. What should the program print, and where in the code should you check for it?

7. Medium. In the O(n log n) LIS, explain why lower_bound must be used for the strict version. Use the values 2 2 to show what goes wrong with upper_bound.

8. Medium. Explain why keeping two rows is enough for LCS, and describe where the diagonal value comes from.

9. Hard. Count the number of longest increasing subsequences, not just their length. For 1 3 5 2 4 6, the length is 4, and there are three of them. Describe a second array that counts the ways, and explain how to combine the counts when two earlier positions give the same best length.

10. Hard. The minimum number of deletions needed to make a string a palindrome equals the length of the string minus the length of its longest palindromic subsequence. The longest palindromic subsequence of s equals the LCS of s and its reverse. Use this to find the answer for abca, and say which letters you would delete.

What you now know

• A two-dimensional table has one cell for each pair of indexes, and its loops go row by row so that the neighbours are ready.
• Grid paths add the cell above and the cell to the left, and a wall contributes zero.
• A subsequence keeps the order but may skip letters, and a substring must be contiguous.
• LCS extends a match when the last letters agree, and otherwise keeps the better of two shorter answers.
• The LCS table has an extra row and column for the empty prefix, which is why the code reads a[i - 1].
• The longest increasing subsequence needs the maximum over all positions, not the last one.
• A tails array with binary search solves the strict LIS in O(n log n) time.
• The next lesson applies the same ideas to edit distance and to string problems such as palindromes.