Algorithms

Longest Common Subsequence — Tabulation

MediumAug 18, 2026dynamic-programmingstringslongest-common-subsequencetabulation

The memo table again, filled in index order instead of discovered by recursion — and named `lcsTopDown` while doing bottom-up, which is the second time this exact mislabel has shown up in the ladder. The substantive change is that the border cells recursion never touched now get written explicitly, so every one of the `(m+1) * (n+1)` cells holds a real answer. That completeness is what makes reconstructing the subsequence itself possible.

The problem

Same problem, iteratively: `lcsTopDown(stringA, stringB, lenA, lenB)` returns the length of the longest common subsequence, with no recursion and no stack.

`"abcde"` and `"ace"` still return `3`, and the answer lands in `memo[5][3]` — the bottom-right corner of a grid where every other cell is also the correct answer to a smaller pair of prefixes.

The approach

The naming first, because it's the same swap as the knapsack entry: this function is bottom-up tabulation, not top-down. Top-down is the previous entry — start at the answer, recurse toward the base cases, cache on the way back. This starts at the base cases and builds toward the answer. Two files into two different ladders now carry the same wrong label, which suggests the mistake is in the template being copied rather than in either problem.

The two seeding loops are the recursive base case written as data instead of an `if`. Row `0` is 'A's prefix is empty' and column `0` is 'B's prefix is empty', both worth `0`, and they overlap harmlessly at `memo[0][0]` because both write the same value — unlike the knapsack minimisation entries, where the overlap was load-bearing and the loop order mattered. Here it genuinely doesn't.

Both loops are also technically redundant, which is worth naming rather than silently keeping. `Array(lenB + 1).fill(0)` instead of `.fill(null)` at the allocation would leave every border cell correct and make both loops dead code. Keeping them is defensible — they're the base case stated in the same language the recursion stated it in, and the next reader converting a different recursion will look for exactly that — but it's a documentation choice, not a correctness one.

The recurrence is the recursion with calls replaced by lookups: `1 + memo[i-1][j-1]` for the match, `Math.max(memo[i][j-1], memo[i-1][j])` for the mismatch. Note the mismatch reads one cell from the previous row and one from the current row, a few columns back — both already written by the time `(i, j)` is reached, which is exactly what `i` outer and `j` inner buys. Every dependency points up, left, or up-left; nothing points forward.

That dependency pattern also exposes the standard optimisation and its cost. Only the previous row and the current row's left neighbour are ever read, so the grid collapses to two rows for `O(min(m, n))` space if you swap the arguments to put the shorter string on the inner axis. The full table is kept because walking backwards from the corner — diagonally on a match, toward the larger neighbour otherwise — is what reconstructs the actual subsequence rather than its length. Collapse the grid and you keep the number and lose the string.

The solution

export function lcsTopDown(stringA, stringB, lenA, lenB) {
  // initialize the first row with 0
  const memo = Array.from({ length: lenA + 1 }, () =>
    Array(lenB + 1).fill(null),
  );

  // initialize the first row with 0
  for (let i = 0; i <= lenA; i++) {
    memo[i][0] = 0;
  }

  // initialize the first column with 0
  for (let j = 0; j <= lenB; j++) {
    memo[0][j] = 0;
  }

  // implementation
  for (let i = 1; i <= lenA; i++) {
    for (let j = 1; j <= lenB; j++) {
      if (stringA[i - 1] == stringB[j - 1]) {
        memo[i][j] = 1 + memo[i - 1][j - 1];
      } else {
        memo[i][j] = Math.max(memo[i][j - 1], memo[i - 1][j]);
      }
    }
  }

  return memo[lenA][lenB];
}

Time O(m * n)Space O(m * n)

What stuck

The memoized and tabulated versions compute the same grid and differ only in who chooses the fill order. Recursion discovers it lazily and pays in stack frames, null checks and call overhead; the loops hard-code it in the bounds and pay nothing. The stack depth ceiling disappearing matters more than it sounds — the recursive version is `O(m + n)` deep, which is fine for words and not for files.
Two loops that write values a different allocation would have produced for free are documentation, and that's a legitimate reason to keep them — but it should be a decision. Initialisation that looks necessary and isn't is how the dead row-`1` loop in the coin change entry survived, and the difference between the two cases is whether the next reader can tell at a glance.
The loop order is chosen by the dependency arrows, not by convention. Up, left and up-left all point at cells already written when `i` is outer and `j` is inner; any order with that property works and any order without it reads garbage. Deriving the order from the recurrence is more reliable than remembering which loop goes outside.
Space optimisation and answer reconstruction pull in opposite directions. Two rows gets the length in `O(min(m, n))` space; the full grid gets the actual subsequence by tracing back from the corner. Which one is right depends entirely on whether the caller wanted a number or a string, and that's a question worth asking before collapsing anything.

All entries