Search
⌘K
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
The solution uses bottom-up dynamic programming to solve the problem. The solution is based on the observation that the size of the largest square ending (bottom-right corner) at a particular cell is equal to the minimum of the sizes of the largest squares ending at the three adjacent cells plus 1.
We create a 2D integer array dp of size (r + 1) x (c + 1) where r is the number of rows in the input array and c is the size of each row. dp[i][j] stores the side length of the largest square ending at the cell matrix[i - 1][j - 1]. All elements of dp are initialized to 0.
Visualization
Python
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 then use a nested loop to iterate over the input array. For each cell matrix[i - 1][j - 1], we check if the cell contains a 1. If it does, we update dp[i][j] to the minimum of the sizes of the largest squares ending at the three adjacent cells plus 1. We also update a variable max_side to store the maximum side length of the largest square we have found so far.
Visualization
Python
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
Python
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 of the loop, max_side contains the side length of the largest square containing only 1's in the input array. The area of the square is max_side * max_side.
Solution
Try these examples:
Visualization
Python
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.