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
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; }}Video 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.