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.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6public:
7 int maximalSquare(vector<vector<char>>& matrix) {
8 if (matrix.empty()) return 0;
9 int m = matrix.size(), n = matrix[0].size();
10 vector<vector<int>> dp(m+1, vector<int>(n+1, 0));
11 int max_side = 0;
12 for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (matrix[i-1][j-1] == '1') {
dp[i][j] = min({dp[i-1][j], dp[i][j-1], dp[i-1][j-1]}) + 1;
max_side = max(max_side, dp[i][j]);
}
}
}
return max_side * max_side;
}
};The C++ solution follows a similar logic to the C solution but uses vectors to manage the dynamic programming table, allowing for easy resizing. The main loop iterates through the matrix, updating the DP table and tracking the largest square.
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)
1Watch 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.
This JavaScript solution echoes the C++ and Python optimizations, transferring the current row `int` array to the previous tracker, renewing for every new row cycle. Its efficiency cuts down on excess element usage.