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

Maximal Square

Core idea: A square's size is decided by its weakest edge. If a cell (i, j) holds a 1, the biggest all-1 square ending there (bottom-right corner) can only be as large as the smallest of the three squares that meet at its top, left, and top-left neighbors — plus one for the cell itself. So instead of re-scanning the grid for every candidate square, we let each cell read three already-computed answers and add one.

Problem, rephrased

Forget the textbook phrasing. Here's the scenario:

You're laying out a data-center floor as a grid of tiles. Each tile is either usable ('1') or blocked ('0' — a pillar, a vent, dead space). You need to drop in one square server rack, and the rack must sit entirely on usable tiles. Question: what's the area of the largest square rack that fits?

You're given a binary matrix grid of characters '0' and '1' with m rows and n columns. Return the area (side length squared) of the largest axis-aligned square consisting only of '1's.

Input grid Output Why
[["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 4 a 2×2 block of 1s fits; side 2 → area 4
[["0","1"],["1","0"]] 1 no 2×2 block exists; best is a single 1 → area 1
[["0"]] 0 no 1 anywhere → no square at all

Note the values are characters ("1", not 1) — a classic LeetCode gotcha when you compare.

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.