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

Core idea: lay the string s along one axis and the pattern p along the other, and ask of every prefix pair "does s[:i] match p[:j]?". Every cell answers from cells above and to the left — and the only interesting cell is '*', which gets two transitions because a star can either swallow one more character of s (look up) or match nothing at all (look left).

Problem, rephrased

You're given an input string s and a glob-style pattern p. The pattern may contain two special characters:

  • '?' matches exactly one arbitrary character.
  • '*' matches any sequence of characters — zero, one, or many.

Return True if and only if p matches the entire string s — not a prefix, not a substring, the whole thing, edge to edge. Every other character in p is a literal that must match itself.

s p Match? Why
"aa" "a" False "a" covers only the first character; the trailing a is unmatched
"aa" "*" True one '*' absorbs the whole string
"cb" "?a" False '?' eats c, but literal a ≠ b
"adceb" "*a*b" True first *="", a=a, second *="dce", b=b
"acdcb" "a*c?b" False no split of * leaves c?b lined up against the tail
"" "***" True a run of stars can each match the empty string

The second-to-last row is the trap: it looks matchable, but once you try every split point of the lone * you find none of them line up c?b against the suffix. That "try every split" is exactly what the DP does in one pass.

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.