Date and Time: Feb 9, 2025, 21:30 (EST)
Link: https://leetcode.com/problems/maximal-square
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.
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
-
m == matrix.length -
n == matrix[i].length -
1 <= m, n <= 300 -
matrix[i][j]is'0'or'1'.
We can use dp table to keep track of the maximum square that we can take from matrix[r][c]. If matrix[r][c] == 1, we find the minimum of (r, c)'s neighbors + 1. Because the minimum means the value (r, c)'s neighbors at least have. Also update ans = max(ans, dp[r+1][c+1]) everytime. Finally, return ans * ans for the maximum square.
[1, 1, 1]
[1, 2, 2]
[1, 2, 3]
area = 3
if matrix[r][c] == 1, check its top-left, top, left neighbors, update dp[r][c] = min(three neighbors) + 1. Because if the min neighbor is 0 and we know matrix[r][c] == 1, so we can have at least one square with area 1. Same thing, if min == 1, that means all three neighbors are at least 1, so plus current grid, we can have 1 + 1 = 2 area.
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
# Use dp to find the max radius of square, we add the base row and col full of 0s
# Recurrence Relation: if matrix[r][c] == 1: dp[r][c] = min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]) + 1
# TC: O(m*n), SC: O(m*n)
rows, cols = len(matrix), len(matrix[0])
dp = [[0] * (cols+1) for _ in range(rows+1)]
ans = 0
# Fill out dp
for r in range(rows):
for c in range(cols):
if matrix[r][c] == '1':
dp[r+1][c+1] = min(dp[r][c+1], dp[r+1][c], dp[r][c]) + 1
ans = max(ans, dp[r+1][c+1])
# Return the area
return ans * ansTime Complexity: $O(mn)$
Space Complexity: $O(mn)$
