You are given an m x n grid matrix filled with the characters "0" and "1". Find the largest square that contains only "1" cells and return its area.
- 1 <= m, n <= 300
- matrix[i][j] is "0" or "1"
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force picks every cell as a top left corner and grows a square while it stays all ones, which is about O((mn)^2). DP does much better. State: dp[i][j] is the side length of the biggest square of ones with bottom right corner at (i, j). Recurrence: if the cell is "1", dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]), because a square of side k at (i, j) needs squares of side k - 1 ending at all three neighbours; if the cell is "0", it is 0. Base case: cells outside the grid count as 0, so the first row and column are just 0 or 1. The answer is the square of the largest side seen.
Algorithm
- Keep a 1D array
dpof sizen + 1(index 0 is a zero border) and a variablediagfor the old up left value. - For each row, reset
diag = 0; for each columnj, savetemp = dp[j+1](the cell above). - If the cell is "1", set
dp[j+1] = 1 + min(dp[j+1], dp[j], diag)and update the best side; otherwise set it to 0. - Set
diag = tempand move on. Returnbest * best.
O(m * n)Space: O(n)"1" (or '1' in Java and C++), not the number 1.class Solution: def maximalSquare(self, matrix: List[List[str]]) -> int: n = len(matrix[0]) dp = [0] * (n + 1) # dp[j + 1]: side of best square ending at column j best = 0 for row in matrix: diag = 0 # old value of the up left cell for j in range(n): temp = dp[j + 1] # value from the row above if row[j] == "1": dp[j + 1] = 1 + min(diag, dp[j], dp[j + 1]) best = max(best, dp[j + 1]) else: dp[j + 1] = 0 diag = temp return best * best