Search
⌘K
Get Premium
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
Your account is free and you can post anonymously if you choose.