Dynamic Programming

Maximal Square

medium

DESCRIPTION (inspired by Leetcode.com)

Given an m x n 2D matrix with only 0's and 1's, write a function to return the area of the largest square containing only 1's.

Input:

matrix = [
[0, 0, 1, 0, 0],
[1, 1, 1, 0, 1],
[0, 1, 1, 0, 0]
]

Output:

Code Editor

Run your code to see results here

Have suggestions or found something wrong?

Explanation

Building Intuition

Let's say we're scanning through a binary matrix and we land on a cell that contains a 1. We want to know: what's the largest square of all 1's that has this cell as its bottom-right corner?

If the cell is on the first row or first column, the answer is easy, it would be at most a 1x1 square (just the cell itself). But what about cells deeper in the matrix?

Consider this small example. We're looking at the highlighted cell and want to know the largest square ending there:

To form a square of side length k ending at a cell, three things must all be true:

The cell above it must be able to form a square of at least side k - 1 (enough 1's stretching up)
The cell to the left must be able to form a square of at least side k - 1 (enough 1's stretching left)
The cell diagonally above-left must be able to form a square of at least side k - 1 (enough 1's filling the interior)

If any one of those three neighbors has a smaller square, that becomes the bottleneck. The current cell's square can only be one bigger than the smallest of the three.

Why the Minimum?

Imagine the three neighbors have square sizes of 3, 2, and 3. You might think the answer is 4 (biggest neighbor + 1), but it's actually 3 (smallest neighbor + 1). Why?

The square ending at the current cell is built by extending squares from those three directions. If any direction can't support a large enough square, the whole thing collapses.

The Recurrence Relation

Here's the formal recurrence, we define dp[i][j] as the side length of the largest square of all 1's whose bottom-right corner is at cell (i, j).

if matrix[i][j] == '1':
    dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
else:
    dp[i][j] = 0

Base cases: For cells in the first row or first column, dp[i][j] is just 1 if the cell contains a 1, and 0 otherwise. There's no room to form anything bigger than a 1x1 square on the edges.

The answer is max_side * max_side, where max_side is the largest value in the entire dp table.

Bottom-Up Solution

Now we can implement this. We create a 2D array dp of size (r + 1) x (c + 1) (padded by one row and column to avoid boundary checks). dp[i][j] stores the side length of the largest square ending at matrix[i - 1][j - 1]. Everything starts at 0.

Visualization


def maximal_square(matrix):
  if not matrix:
    return 0
  r = len(matrix)
  c = len(matrix[0])
  dp = [[0] * (c + 1) for _ in range(r + 1)]
  max_side = 0
  for i in range(1, r + 1):
    for j in range(1, c + 1):
      if matrix[i - 1][j - 1] == 1:
        top = dp[i - 1][j]
        left = dp[i][j - 1]
        diag = dp[i - 1][j - 1]
        dp[i][j] = min(top, left, diag) + 1
        max_side = max(max_side, dp[i][j])
  return max_side * max_side

maximal square

0 / 1

We iterate through each cell. When we find a 1, we apply our recurrence — take the min of the three neighbors and add 1. We also track max_side as we go.

Visualization


def maximal_square(matrix):
  if not matrix:
    return 0
  r = len(matrix)
  c = len(matrix[0])
  dp = [[0] * (c + 1) for _ in range(r + 1)]
  max_side = 0
  for i in range(1, r + 1):
    for j in range(1, c + 1):
      if matrix[i - 1][j - 1] == 1:
        top = dp[i - 1][j]
        left = dp[i][j - 1]
        diag = dp[i - 1][j - 1]
        dp[i][j] = min(top, left, diag) + 1
        max_side = max(max_side, dp[i][j])
  return max_side * max_side

i = 1 | j = 1

0 / 2

Calculating size of the maximal square when `matrix[i - 1][j - 1] = 1`

Visualization


def maximal_square(matrix):
  if not matrix:
    return 0
  r = len(matrix)
  c = len(matrix[0])
  dp = [[0] * (c + 1) for _ in range(r + 1)]
  max_side = 0
  for i in range(1, r + 1):
    for j in range(1, c + 1):
      if matrix[i - 1][j - 1] == 1:
        top = dp[i - 1][j]
        left = dp[i][j - 1]
        diag = dp[i - 1][j - 1]
        dp[i][j] = min(top, left, diag) + 1
        max_side = max(max_side, dp[i][j])
  return max_side * max_side

i = 3 | j = 4

0 / 2

Another maximal square calculation when `matrix[i - 1][j - 1] = 1`

At the end, max_side has the side length of the largest square, and the area is max_side * max_side.

Solution

Try these examples:

Visualization


def maximal_square(matrix):
  if not matrix:
    return 0
  r = len(matrix)
  c = len(matrix[0])
  dp = [[0] * (c + 1) for _ in range(r + 1)]
  max_side = 0
  for i in range(1, r + 1):
    for j in range(1, c + 1):
      if matrix[i - 1][j - 1] == 1:
        top = dp[i - 1][j]
        left = dp[i][j - 1]
        diag = dp[i - 1][j - 1]
        dp[i][j] = min(top, left, diag) + 1
        max_side = max(max_side, dp[i][j])
  return max_side * max_side

maximal square

0 / 48

What is the time complexity of this solution?

O(log n)

O(n * logn)

O(m * n)

O(n²)

Mark as read

Next: Longest Increasing Subsequence