Your free access ends in 7 days — and you haven’t tried it yet. Watch one algorithm run, start to finish. It takes about two minutes.

Try one problem
0
Problem

Maximal Square

LeetCode #221Medium
Grid DP · dp[i][j] = min(up, left, diag) + 1

Given a binary matrix of 0s and 1s, find the largest square consisting entirely of 1s and return its area.

Asked atAmazonGoogleApple
step 1 / 30
4 × 5 grid · dp[i][j] = side of largest all-1 square ending at (i,j)
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
·
Grid DP (tabulation)
▸
1dp = R × C grid, best = 0
2first row / col: dp = source value
3for i in 1..R−1: for j in 1..C−1:
4    if grid[i][j] == 0: dp[i][j] = 0
5    else dp[i][j] = min(dp[i−1][j], dp[i][j−1], dp[i−1][j−1]) + 1
6    best = max(best, dp[i][j])
7return best * best
state
  • grid4×5
  • statedp[i][j] = max all-1 square side ending here

line 1Find the largest square made entirely of 1s. KEY IDEA: let dp[i][j] = the side length of the biggest all-1 square whose BOTTOM-RIGHT corner sits at (i, j). The answer is (max dp)². Source 1s sit where squares can grow; 0s force dp = 0.