Skip to main content

221. Maximal Square

medium

Given a binary matrix, find the side length of the largest square made entirely of 1s. The recurrence dp[i][j] = 1 + min(top, left, top-left) is one of the most quotable lines in interview DP.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Constraints

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] is '0' or '1'.

Examples

Example 1

Input
matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output
4

Example 2

Input
matrix = [["0","1"],["1","0"]]
Output
1

Example 3

Input
matrix = [["0"]]
Output
0

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

dp[i][j] = the side length of the largest all-1s square whose bottom-right corner is at (i, j).

Hint 2

If matrix[i][j] == 0, dp[i][j] = 0. Otherwise dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).

Hint 3

Track the global max side as you fill the table; the answer is side * side.

Hint 4

Space optimization: only the previous row + the most recent diagonal value are needed.

Solution approach

Reveal approach

Bottom-up DP. Define dp[i][j] as the side length of the largest all-1s square with bottom-right at (i, j). For the first row and first column, dp[i][j] = matrix[i][j] (interpreted as int). For every inner cell where matrix[i][j] == 1, dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]); zero cells stay zero. Track maxSide across the fill. Return maxSide * maxSide. Why the min of three: the new square is limited by the smallest square abutting it from the three neighbors that share a side or corner. Space optimization: keep a 1D dp row plus a single 'previous diagonal' scalar.

Complexity

Time
O(m * n)
Space
O(n)

Related patterns

  • dynamic-programming
  • grid-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Apple
  • Microsoft
  • Meta

Practice these live with InterviewChamp.AI

Drill Maximal Square and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →