Dynamic Programming
Maximal Square
medium
Count: 10
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:
4
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] = 0Base 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 0r = len(matrix)c = len(matrix[0])dp = [[0] * (c + 1) for _ in range(r + 1)]max_side = 0for 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) + 1max_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 0r = len(matrix)c = len(matrix[0])dp = [[0] * (c + 1) for _ in range(r + 1)]max_side = 0for 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) + 1max_side = max(max_side, dp[i][j])return max_side * max_side
i = 1 | j = 1
0 / 2
Visualization
def maximal_square(matrix):if not matrix:return 0r = len(matrix)c = len(matrix[0])dp = [[0] * (c + 1) for _ in range(r + 1)]max_side = 0for 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) + 1max_side = max(max_side, dp[i][j])return max_side * max_side
i = 3 | j = 4
0 / 2
At the end, max_side has the side length of the largest square, and the area is max_side * max_side.
Solution
Visualization
Try these examples:
def maximal_square(matrix):if not matrix:return 0r = len(matrix)c = len(matrix[0])dp = [[0] * (c + 1) for _ in range(r + 1)]max_side = 0for 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) + 1max_side = max(max_side, dp[i][j])return max_side * max_side
maximal square
0 / 48
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the input array. We iterate over each cell once, and for each cell, we perform a constant amount of work.
Space Complexity: O(m * n) where m is the number of rows and n is the number of columns. We use a 2D array dp of size (m + 1) x (n + 1) to store the side length of the largest square ending at each cell.
Mark as read
Unlock Premium Coding Content
Reading Progress
On This Page
Your account is free and you can post anonymously if you choose.