DSA problem
Maximal Square
Given an m x n binary matrix filled with 0s and 1s, find the largest square containing only 1s and return its area.
A naive approach checks every possible square: pick a top-left corner, an edge length, and verify the whole square is all ones. That is O(m * n * min(m, n)^3) and far too slow for non-trivial grids. A better but still wasteful idea precomputes the 2-D prefix sum so each rectangle check is O(1), but you still enumerate O(m * n * min(m, n)) candidate squares.
The optimal technique is a beautiful 2-D DP. Define dp[i][j] as the side length of the largest all-ones square whose bottom-right corner is (i, j). If matrix[i][j] == 0, the cell cannot anchor any square so dp[i][j] = 0. Otherwise dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]). The intuition is that an all-ones square of side s ending here exists iff three smaller squares of side s - 1 ending at the three neighbors all exist; the limiting factor is the smallest of the three.
Tracking the running maximum of dp[i][j] gives the side length of the largest square; squaring it yields the area. The transition only needs the previous row plus one extra value (the old dp[i - 1][j - 1] that gets overwritten when dp[i][j - 1] is computed), so the DP compresses to a single 1-D array of length n with a single integer holding the diagonal predecessor. Total: O(m * n) time, O(n) space.
Examples
matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]4matrix = [["0","1"],["1","0"]]1matrix = [["0"]]0Constraints
- m == matrix.length
- n == matrix[i].length
- 1 <= m, n <= 300
- Each cell of `matrix` is either the character '0' or '1'.
- The answer must be the area (side^2) of the largest all-ones square.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.