Maximal Square
MedPrompt
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: 4Example 2:
Input: matrix = [["0","1"],["1","0"]]
Output: 1Example 3:
Input: matrix = [["0"]]
Output: 0
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 300matrix[i][j]is'0'or'1'.
Approaches
3 approaches with complexity analysis and trade-offs.
Check every possible square in the matrix by iterating through each cell as a potential top-left corner of a square and expanding the size until we find the largest valid square.
Algorithm
- Iterate through each cell in the matrix
- If a cell contains '1', try to expand it into a square
- For each expansion:
- Check if all cells in the new row and column are '1's
- If yes, continue expanding
- If no, stop and update maximum square length if necessary
- Return the area of the largest square found
Walkthrough
For each cell in the matrix that contains '1', we try to expand it into a square by checking if all cells within the potential square are '1's. We keep track of the maximum square size found.
class Solution { public int maximalSquare(char[][] matrix) { if (matrix == null || matrix.length == 0) return 0; int rows = matrix.length; int cols = matrix[0].length; int maxSquareLen = 0; for (int i = 0; i < rows; i++) { for (int j = 0; j < cols; j++) { if (matrix[i][j] == '1') { int squareLen = 1; boolean flag = true; // Try to expand the square while staying within bounds while (i + squareLen < rows && j + squareLen < cols && flag) { // Check the new row and column to be added for (int k = j; k <= j + squareLen; k++) { if (matrix[i + squareLen][k] == '0') { flag = false; break; } } for (int k = i; k <= i + squareLen; k++) { if (matrix[k][j + squareLen] == '0') { flag = false; break; } } if (flag) squareLen++; } maxSquareLen = Math.max(maxSquareLen, squareLen); } } } return maxSquareLen * maxSquareLen; }}Complexity
Time
O(m*n*min(m,n)^2) where m and n are the dimensions of the matrix. For each cell, we might need to check up to min(m,n) cells in both directions.
Space
O(1) as we only use a constant amount of extra space
Trade-offs
Pros
Simple to understand and implement
No extra space required except for a few variables
Cons
Very inefficient for large matrices
Performs redundant checks on the same cells multiple times
Time complexity is cubic in the worst case
Use dynamic programming to build the solution by maintaining a dp table where dp[i][j] represents the side length of the largest square ending at position (i,j).
Algorithm
- Create a dp table with dimensions (m+1) x (n+1)
- For each cell (i,j) in the original matrix:
- If the cell contains '1', set dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
- If the cell contains '0', dp[i][j] remains 0
- Keep track of the maximum value in dp table
- Return the square of the maximum value
Walkthrough
We create a dp table where dp[i][j] represents the side length of the largest square that can be formed with (i,j) as the bottom-right corner. The value at each position depends on the minimum of the values at the top, left, and top-left positions plus 1.
class Solution { public int maximalSquare(char[][] matrix) { if (matrix == null || matrix.length == 0) return 0; int rows = matrix.length; int cols = matrix[0].length; int[][] dp = new int[rows + 1][cols + 1]; int maxSquareLen = 0; for (int i = 1; i <= rows; i++) { for (int j = 1; j <= cols; j++) { if (matrix[i-1][j-1] == '1') { dp[i][j] = Math.min( Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1] ) + 1; maxSquareLen = Math.max(maxSquareLen, dp[i][j]); } } } return maxSquareLen * maxSquareLen; }}Complexity
Time
O(m*n) where m and n are the dimensions of the matrix. We only need to visit each cell once.
Space
O(m*n) to store the dp table
Trade-offs
Pros
Much more efficient than brute force approach
Avoids redundant calculations
Solves the problem in a single pass through the matrix
Cons
Requires additional space for the dp table
May not be optimal for very sparse matrices with few 1's
Optimize the space usage of the dynamic programming approach by using only a 1D array instead of a 2D matrix, since we only need the previous row's values.
Algorithm
- Create a 1D dp array of length n+1
- For each cell in the matrix:
- Store the previous diagonal value
- If current cell is '1', update dp[j] using the minimum of previous values
- If current cell is '0', set dp[j] to 0
- Update the previous diagonal value for next iteration
- Keep track of maximum value seen
- Return the square of the maximum value
Walkthrough
We can optimize the space usage by observing that we only need the previous row's values and the previous column's value to calculate the current cell. We can use a 1D array and keep track of the previous diagonal value separately.
class Solution { public int maximalSquare(char[][] matrix) { if (matrix == null || matrix.length == 0) return 0; int rows = matrix.length; int cols = matrix[0].length; int[] dp = new int[cols + 1]; int maxSquareLen = 0; int prev = 0; for (int i = 1; i <= rows; i++) { for (int j = 1; j <= cols; j++) { int temp = dp[j]; if (matrix[i-1][j-1] == '1') { dp[j] = Math.min(Math.min(dp[j], dp[j-1]), prev) + 1; maxSquareLen = Math.max(maxSquareLen, dp[j]); } else { dp[j] = 0; } prev = temp; } } return maxSquareLen * maxSquareLen; }}Complexity
Time
O(m*n) where m and n are the dimensions of the matrix
Space
O(n) where n is the number of columns in the matrix
Trade-offs
Pros
Most space-efficient approach
Same time complexity as regular dynamic programming
Better cache performance due to smaller memory footprint
Cons
Slightly more complex to understand and implement
Still requires O(n) extra space
Solutions
Solution
public class Solution { public int MaximalSquare(char[][] matrix) { int m = matrix.Length, n = matrix[0].Length; var dp = new int[m + 1, n + 1]; int mx = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (matrix[i][j] == '1') { dp[i + 1, j + 1] = Math.Min(Math.Min(dp[i, j + 1], dp[i + 1, j]), dp[i, j]) + 1; mx = Math.Max(mx, dp[i + 1, j + 1]); } } } return mx * mx; }}class Solution {public int maximalSquare(char[][] matrix) { int m = matrix.length, n = matrix[0].length; int[][] dp = new int[m + 1][n + 1]; int mx = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (matrix[i][j] == '1') { dp[i + 1][j + 1] = Math.min(Math.min(dp[i][j + 1], dp[i + 1][j]), dp[i][j]) + 1; mx = Math.max(mx, dp[i + 1][j + 1]); } } } return mx * mx; }}class Solution {public: int maximalSquare(vector<vector<char>> &matrix) { int m = matrix.size(), n = matrix[0].size(); vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); int mx = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (matrix[i][j] == '1') { dp[i + 1][j + 1] = min(min(dp[i][j + 1], dp[i + 1][j]), dp[i][j]) + 1; mx = max(mx, dp[i + 1][j + 1]); } } } return mx * mx; }};''' eg. a 10*10 sqaure with full of 1s this square move 1 line down this square move 1 line right so there needs an extra single 1 at bottom right, to make it a larger full square ''' class Solution : def maximalSquare ( self , matrix : List [ List [ str ]]) -> int : m , n = len ( matrix ), len ( matrix [ 0 ]) dp = [[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )] mx = 0 for i in range ( m ): for j in range ( n ): if matrix [ i ][ j ] == '1' : dp [ i + 1 ][ j + 1 ] = 1 + min ( dp [ i ][ j + 1 ], dp [ i + 1 ][ j ], dp [ i ][ j ]) mx = max ( mx , dp [ i + 1 ][ j + 1 ]) return mx * mxVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.