</> 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.

Edit Distance

Core idea: Lay the two words on the axes of a grid and let dp[i][j] be the minimum number of single-character edits to turn the first i letters of word1 into the first j letters of word2. The last two letters either match — then they cost nothing and you copy the answer from the diagonal dp[i-1][j-1] — or they don't, and you pay 1 plus the cheapest of the three things you could do to fix that last position: delete (come from dp[i-1][j]), insert (come from dp[i][j-1]), or replace (come from dp[i-1][j-1]). Fill the grid row by row from the trivial "one string is empty" base cases, and the bottom-right cell is the Levenshtein distance.

Problem, rephrased

You are a relentless copy editor. Someone hands you a word, word1, and the word it was supposed to be, word2. You may fix the misspelling using only three moves, each costing one edit:

  • Insert a single character anywhere.
  • Delete a single character.
  • Replace one character with another.

Your job: report the fewest edits that transform word1 into word2. That count is the famous Levenshtein distance (LeetCode 72).

Transforming horse into ros in 3 edits: replace h with r, delete r, delete e

Inputs / outputs

word1 word2 min edits one cheapest script
"horse" "ros" 3 replace h→r, delete r, delete e
"intention" "execution" 5 delete, replace ×3, insert
"abc" "abc" 0 already equal
"" "abc" 3 insert a, b, c
"abc" "" 3 delete a, b, c
"abc" "xyz" 3 replace each of the three

You return a single integer. You never have to report the script of edits — only its length — which is exactly what makes the clean DP recurrence legal.

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.