</> MAANG.io
Sign in
Level101201301
coding interview · 101

Foundations

Master coding interviews with comprehensive coverage of data structures, algorithms, and problem-solving techniques. Progress from fundamentals to advanced topics with expertly curated content.

0/255 solved 0% complete

Grid & 2D DP

What is this?

Some problems need two indices instead of one — your position in a grid, or how much of each of two strings you have used so far. Here each answer lives in a 2D table dp[i][j] and is built from a few nearby cells you already filled, like figuring out the cheapest path to a square from the squares just above and to its left. Once a cell is computed it is remembered, so the whole table fills in one sweep without ever redoing a square.

flowchart TD A["Two indices i and j"] --> B["Build a 2D table dp i j"] B --> C["Fill the base row and column"] C --> D["Each cell combines its neighbors"] D --> E["Collapse to a rolling row to save space"]

💡 Fun fact: The two-string version of this table is the engine behind tools you use daily — git diff, spell-checkers, and DNA sequence aligners all compute a longest-common-subsequence or edit-distance grid exactly like the ones in this chapter.

🔓 The 7 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: When the state needs two indices — a position in a grid, or a prefix of each of two strings — the DP becomes a 2D table dp[i][j] filled from neighboring cells. Almost every famous string/grid DP is the same loop with a different "combine" rule: add the neighbors, take the min of three, or extend the diagonal on a match.

One loop, different combine rules

Six grid-DP problems compared: same double loop, different combine rule per problem

Get the base row/column and the direction of dependency right, and a cell just reads already-computed neighbors. Then collapse the table to a rolling row for O(n) space.

The problems

The grid-DP family: 2D DP dp[i][j] from neighbors branches into seven problems from Unique Paths to LCS

  • Unique Paths — the gentle intro: paths = from above + from left.
  • Maximal Square / Minimum Falling Path Sum — min-of-neighbors recurrences over a grid.
  • Paint House — dp[i][color] with an adjacency constraint; state = your last choice.
  • Edit Distance, Longest Common Subsequence, Wildcard Matching — the two-string family: matches glide diagonally; the rest is the per-problem rule (3 operations, max-align, or *'s two transitions).

Key takeaways

  • Two indices ⇒ a 2D table; each cell combines a handful of neighbors.
  • The family shares one loop — only the combine rule and base cases change.
  • Matches move diagonally in two-string DPs (LCS, Edit Distance); mismatches branch.
  • Collapse to a rolling row for O(min(m,n)) space once it works.
  • Why interviewers love it: the 2D table is the most reused DP shape in real interviews (diff, alignment, grids).

Start here: Unique Paths (the template), then Longest Common Subsequence and Edit Distance.

Longest Common Subsequence

Core idea: Walk both strings from the back, comparing the last characters of two prefixes. If they match, that shared character is part of the answer — keep it and recurse on the two shorter prefixes (the diagonal, +1). If they don't match, at least one of those two last characters is useless for this pairing, so throw away one (from either string) and take whichever choice leaves the longer common subsequence. Cache the answer for every (prefix-of-1, prefix-of-2) pair and the exponential search collapses into an m × n table.

Problem, rephrased

Forget the textbook phrasing. Here's the scenario:

Two editors typed up the same paragraph independently, then each made their own edits — inserting, deleting, and rearranging nothing but keeping the original word order intact. You want to measure how much of the original survived in both versions: the longest run of characters (not necessarily next to each other, but in the same relative order) that appears in both texts.

Formally: given two strings text1 and text2, return the length of their longest common subsequence. A subsequence is what's left after deleting zero or more characters without reordering the rest — so "ace" is a subsequence of "abcde" (delete b and d), but "aec" is not (wrong order). A common subsequence is one that's a subsequence of both strings. If there is no common subsequence, the answer is 0.

text1 text2 LCS length A longest common subsequence
"abcde" "ace" 3 "ace"
"abc" "abc" 3 "abc" (identical strings)
"abc" "def" 0 "" (nothing in common)

Note we return the length, not the subsequence itself (though the table can reconstruct one — more on that below). Let m = len(text1) and n = len(text2).

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.