Medium Problemsstringoptimization

Longest Common Increasing Subsequence

Given two arrays, find the length of the longest sequence of values that is simultaneously a common subsequence of both arrays and strictly increasing.

Do this lesson first: longest common subsequence

Example input

A = [2, 3, 6, 4, 1, 5, 7], B = [2, 7, 6, 1, 5, 3, 4, 5, 3, 7] (the first 10 of B's 11 items)

Expected output

5

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

dp[i][j], defined only where A[i] = B[j], is the length of the longest common increasing subsequence that ENDS on that value, taken at position i of A and position j of B. Positions count from 0, and unlike longest-common-subsequence there is no empty-prefix row or column: dp[i][j] speaks about A[i] and B[j] themselves, which is why row 3's gutter reads 3 4, position 3 of A holding the value 4. Pinning the end is what makes a recurrence possible, and it forces the match. The last value of a common subsequence sits at some position in A and some position in B, and it is the same value in both, so a chain can only end on a pair where A[i] = B[j]. Every other position is a dot, and a dot is not a 0: it is a pair of positions on which no common increasing subsequence can end at all. This is longest-increasing-subsequence lifted to pairs, with longest-common-subsequence's matching condition added: LIS's dp[i] is the longest increasing chain ending at index i of one array, and here the chain has to end at a position in each array at once. A cell holds a length, not the chain, and since the best chain can end on any matched pair, the answer is the largest cell anywhere.

dp[i][j] = 1 + max(dp[p][q]) over matched pairs with p < i, q < j and A[p] < A[i], or 1 if there are none (defined only where A[i] = B[j])

Ask what came immediately before A[i] in the best chain that ends here. Either nothing did, and this pair starts a chain of its own, of length 1, or some earlier matched pair (p, q) did. That pair has to come strictly before this one in BOTH arrays, p < i and q < j, because a subsequence keeps each array's order, and its value has to be strictly smaller, A[p] < A[i], because the chain increases. Any chain ending at (p, q) can be extended by this pair, and the longest such chain is what dp[p][q] already holds, so each qualifying pair is a candidate worth dp[p][q] + 1, and the cell keeps the largest. Each candidate is one cell, the same one-cell-per-candidate shape longest-increasing-subsequence uses, with the scan running over a rectangle above and to the left instead of a stretch of one array.

No bases. Every live cell is computed, including the ones with no candidate, which compute 1 from nothing and consult no other cell: at the drive size those are dp[0][0], A's first item, with nothing before it in A, and dp[4][3], the 1, with no smaller value anywhere above and to the left of it. A row-major sweep, left to right within each row, is enough, because every candidate sits in a strictly earlier row and the sweep finished that row before starting this one. Sitting strictly to the left as well is what the problem demands, since B's order has to be kept; the sweep does not need it. The flip side is that a cell in the last row is never a candidate for anything, since no row comes after it: dp[6][1] = 2, the chain 2, 7, is a real state that no other cell uses. The answer is the largest cell anywhere, so the sweep keeps the largest value written so far. It is not the last cell, which is a dot at four of the five slider lengths.

Tabulation as drawn: with A of length m and B of length n, each live cell scans the whole rectangle above and to the left of it for candidates, which is O(m × n) work per cell and O(m^2 × n^2) in all. On a 7 by 10 table that costs nothing: at the drive size the 10 live cells consult 20 candidates between them, 8 of them at the answer cell. The production version runs in O(m × n) with one array f over B's positions, where f[j] is the longest chain found so far that ends at B[j]. For each A[i] in turn, sweep B left to right carrying best, the largest f[j] seen so far at a position whose value is below A[i], and wherever B[j] = A[i], raise f[j] to best + 1. That version is not drawn because its running best is a number carried along the sweep rather than a cell, so a comparison would have no cell to point at. Drag the slider and B grows one item at a time while A stays put; the answer goes 3, 4, 4, 5, 5 across lengths 7 to 11. At length 7 the best is 2, 3, 4, ending at dp[3][6]. At 8, B gains a 5, and dp[5][7] = 4 extends that to 2, 3, 4, 5. At 9 the second 3 gives dp[1][8] = 2, and the answer stays 4. At 10 the second 7 gives dp[6][9] = 5. At 11 the second 1 gives dp[4][10] = 1: 1 is A's smallest value, so it can only start a chain, and nothing comes after it in B to extend one.

Time O(m^2 × n^2) as drawn, O(m × n) with a running best per row of ASpace O(m × n), or O(n) for the running-best version

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

No bases. Every live cell is computed, including the ones with no candidate, which compute 1 from nothing and consult no other cell: at the drive size those are dp[0][0], A's first item, with nothing before it in A, and dp[4][3], the 1, with no smaller value anywhere above and to the left of it. A row-major sweep, left to right within each row, is enough, because every candidate sits in a strictly earlier row and the sweep finished that row before starting this one. Sitting strictly to the left as well is what the problem demands, since B's order has to be kept; the sweep does not need it. The flip side is that a cell in the last row is never a candidate for anything, since no row comes after it: dp[6][1] = 2, the chain 2, 7, is a real state that no other cell uses. The answer is the largest cell anywhere, so the sweep keeps the largest value written so far. It is not the last cell, which is a dot at four of the five slider lengths.

Rows ↓
Cols →

0 2

1 7

2 6

3 1

4 5

5 3

6 4

7 5

8 3

9 7

0 2

1

·

1 3

·

2

·

2

·

2 6

·

2

·

3 4

·

3

·

4 1

·

1

·

5 5

·

2

·

4

·

6 7

·

2

·

5

Rows ↓A = [2, 3, 6, 4, 1, 5, 7]: row i is A[i], counting from 0

Cols →B, a prefix of [2, 7, 6, 1, 5, 3, 4, 5, 3, 7, 1]: column j is B[j], counting from 0

longest-common-increasing-subsequence.ts

1function lcis(a, b) {
2 const m = a.length, n = b.length;
3 const dp = a.map(() => new Array(n).fill(0)); // 0 marks a dot
4 let best = 0;
5 for (let i = 0; i < m; i++) {
6 for (let j = 0; j < n; j++) {
7 if (a[i] !== b[j]) continue;
8 let longest = 0;
9 for (let p = 0; p < i; p++) {
10 for (let q = 0; q < j; q++) {
11 if (a[p] === b[q] && a[p] < a[i]) longest = Math.max(longest, dp[p][q]);
12 }
13 }
14 dp[i][j] = 1 + longest;
15 best = Math.max(best, dp[i][j]);
16 }
17 }
18 return best;
19}

Base caseComputedBeing readAnswer

The code, the trap, the variations

longest-common-increasing-subsequence.ts

1function lcis(a, b) {
2 const m = a.length, n = b.length;
3 const dp = a.map(() => new Array(n).fill(0)); // 0 marks a dot
4 let best = 0;
5 for (let i = 0; i < m; i++) {
6 for (let j = 0; j < n; j++) {
7 if (a[i] !== b[j]) continue;
8 let longest = 0;
9 for (let p = 0; p < i; p++) {
10 for (let q = 0; q < j; q++) {
11 if (a[p] === b[q] && a[p] < a[i]) longest = Math.max(longest, dp[p][q]);
12 }
13 }
14 dp[i][j] = 1 + longest;
15 best = Math.max(best, dp[i][j]);
16 }
17 }
18 return best;
19}

Where people go wrong

Dropping the increasing condition: counting every matched pair above and to the left as a candidate, whatever its value. What that computes is a longest common subsequence, built over matched pairs, and on this input it first goes wrong at dp[4][3]. A[4] = B[3] = 1, and dp[2][2] = 2, the chain 2, 6, sits above and to the left, so the cell writes 3 and claims 2, 6, 1: common to both arrays, but not increasing. The correct value is 1. dp[5][4] follows it to 4, for 2, 6, 1, 5, against the correct 2. At length 7 the wrong rule returns 4 against the correct 3. At lengths 8 to 11 it returns 4, 4, 5, 5, the right numbers, because from length 8 on one of the longest common subsequences happens to be increasing (2, 3, 4, 5, then 2, 3, 4, 5, 7). So the answer exposes the bug at one slider length out of five, and at the drive size the answer is right while those two cells are wrong. The second trap is longest-common-subsequence's habit of returning the last cell: here that position is a dot at lengths 7, 8, 9 and 11.

Allow equal neighbours: find the longest common NON-DECREASING subsequence.
One comparison loosens, A[p] < A[i] becomes A[p] <= A[i]. The positions stay strict, p < i and q < j, because one position of an array cannot be used twice. The live cells, the empty base list, the row-major order and the largest-cell answer do not change. Nor does any number on this input: measured at every slider length, both versions give 3, 4, 4, 5, 5. A holds no value twice, so two different rows never hold equal values, and a candidate always sits in a different row. The two 3s in B, at columns 5 and 8, both land in row 1, so even <= cannot chain them. On an A with a repeated value, say A = [2, 2] against B = [2, 2], the strict version gives 1 and the loose one 2.
Return the subsequence itself, not just its length.
The table and its recurrence do not change; each cell also remembers which candidate won. Walk back from the largest cell, following each winner, until a cell with no candidates, and read the values in reverse. At the drive size the walk is dp[6][9], dp[5][7], dp[3][6], dp[1][5], dp[0][0], spelling 2, 3, 4, 5, 7. It needs one stored pointer per cell, not a second rectangle scan. A tie needs a rule, and this table has one: dp[5][4] = 2 can come from dp[0][0] (2, 5) or from dp[4][3] (1, 5). That cell is not on the walk from the answer, so the subsequence printed here is the same either way.
Set B = A: the longest increasing subsequence common to an array and itself.
The recurrence does not change, and the problem collapses into longest-increasing-subsequence, because every increasing subsequence of A is common to A and itself. When A holds no value twice, as this one does, the only matched pairs are the diagonal cells (i, i), a candidate for (i, i) is a diagonal cell (p, p) with p < i and A[p] < A[i], and dp[i][i] is exactly LIS's dp[i]. On this A that is a 7 by 7 table with 7 live cells, whose largest is 5, for 2, 3, 4, 5, 7. The pair state costs 49 positions to hold what a one-dimensional LIS table holds in 7 cells.

Longest Palindromic Subsequence All distinct subset (or subsequence) sums