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
Constraints:
m == matrix.lengthn == matrix[i].length1 <= m, n <= 300matrix[i][j] is '0' or '1'.The key idea in Maximal Square is to determine the size of the largest square submatrix that contains only '1' values. A common and efficient strategy is to use Dynamic Programming. Instead of checking every possible square (which would be expensive), we track the largest square that can end at each cell.
If a cell contains '1', the size of the square ending at that cell depends on its neighboring cells: the top, left, and top-left diagonal. The smallest of those values determines how large the current square can grow. This relationship allows us to build the solution incrementally across the matrix.
Using a DP table, we compute results in a single pass through the grid. The typical implementation runs in O(m × n) time for an m x n matrix, with O(m × n) space. A space-optimized variation can reduce the extra memory to O(n) by keeping only the previous row.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (2D DP Table) | O(m × n) | O(m × n) |
| Space Optimized DP | O(m × n) | O(n) |
take U forward
In this approach, a dynamic programming (DP) table is used to store the size of the largest square whose bottom-right corner is at each cell. For each cell (i, j) with a value of '1', we check its top (i-1, j), left (i, j-1), and top-left (i-1, j-1) neighbors to determine the size of the largest square ending at (i, j). If any of these neighbors are '0', the square cannot extend to include (i, j). The formula is: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. The maximum value in the DP table will be the side length of the largest square, and the area is its square.
Time Complexity: O(m * n), where m is the number of rows and n is the number of columns.
Space Complexity: O(m * n), due to the DP table.
1class Solution:
2 def maximalSquare(self, matrix):
3 if not matrix:
4 return 0
5 m, n = The Python solution initializes a DP table with one extra row and column filled with zeros, to handle boundary conditions without additional checks. It iterates through the matrix, updating the DP table using the given formula and tracking the maximum square side found.
This approach uses a similar DP strategy but optimizes space by utilizing a one-dimensional array instead of a full 2D DP table. The key idea is that while processing the matrix row by row, previous rows' information will be partially redundant. Hence, we can maintain only the current and previous row data in separate arrays or even use a single array with swap states.
Time Complexity: O(m * n)
Space Complexity: O(n)
1public class Solution {
public int MaximalSquare(char[][] matrix) {
if (matrix.Length == 0) return 0;
int m = matrix.Length, n = matrix[0].Length;
int[] prev = new int[n + 1];
int[] current = new int[n + 1];
int maxSide = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i - 1][j - 1] == '1') {
current[j] = Math.Min(Math.Min(prev[j], current[j - 1]), prev[j - 1]) + 1;
maxSide = Math.Max(maxSide, current[j]);
}
}
Array.Copy(current, prev, n + 1);
Array.Clear(current, 0, n + 1);
}
return maxSide * maxSide;
}
}Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Maximal Square is a common matrix and dynamic programming interview question. It tests understanding of DP state transitions, matrix traversal, and space optimization techniques.
The optimal approach uses dynamic programming. For each cell containing '1', we determine the largest square that can end at that cell by looking at the top, left, and top-left neighbors. This reduces the problem to a single pass through the matrix.
Yes. Instead of storing the entire DP matrix, you can keep only the previous row and current row values. This reduces the extra space complexity from O(m × n) to O(n) while maintaining the same time complexity.
A dynamic programming table (2D array) is typically used to store the size of the largest square ending at each cell. This structure allows efficient reuse of previously computed results and helps achieve O(m × n) time complexity.
C# utilizes a similar logic with single dimensional `int` arrays for processing, swapping them with each iteration over rows. Utilizing Array.Copy and Array.Clear to manage elements over iterations.