221. Maximal Square
Problem Description
The problem presents a scenario where you are given a matrix composed of only 0
s and 1
s, which corresponds to a binary grid. Your objective is to discover the largest square formed entirely of 1
s within this matrix and then return the area of that square. This is fundamentally a problem of pattern recognition and optimization, as one needs to efficiently navigate the matrix to recognize the largest square pattern without having to examine every possible square explicitly.
Intuition
The intuitive leap for solving this problem lies in dynamic programming, which allows us to store and reuse the results of subproblems to build up to the final solution effectively. The principle is to traverse the matrix once, and at each cell that contains a 1
, determine the largest square that can be formed ending at that cell. The key observation is that the size of the largest square ending at a cell is limited by the smallest of the adjacent cells to the top, left, and top-left (diagonal). If all of these are parts of squares of 1
s, then the current cell can extend those squares by one more layer.
To achieve this, we initialize an auxiliary matrix dp
with the same dimensions as the input matrix plus an extra row and column for padding, filled with zeros. As we iterate through each cell in the original matrix, we update the corresponding cell in the dp
matrix. If the current cell in the original matrix is a 1
, we look at the dp
values of the adjacent cells mentioned previously – top, left, and top-left – and find the minimum value among them. The dp
value for the current cell is one more than this minimum value, which reflects the size of the largest square that could be formed up to that cell.
Throughout this process, we track the maximum dp
value seen, which corresponds to the size of the largest square of 1
s found. Once the entire matrix has been traversed, this maximum value is squared to give the final area of the largest square since the area is the side length squared, and the side length is what the dp
matrix stores.
Learn more about Dynamic Programming patterns.
Solution Approach
The implementation of the solution involves initializing a dynamic programming (DP) table named dp
. This table dp
is a 2D array with the same number of rows and columns as the input matrix
, plus one extra for each to provide padding. The padding helps to simplify the code, as it allows us not to have special cases for the first row and first column.
Step-by-Step Implementation:
-
Initialization: Create a 2D list
dp
withm + 1
rows andn + 1
columns filled with zeros, wherem
andn
are the row and column counts of the inputmatrix
, respectively. Also, initialize a variablemx
to zero; this will hold the length of the largest square's side found during the DP table fill-up. -
Iterate through matrix: Using two nested loops, iterate through the
matrix
. The outer loop goes through each rowi
, and the inner loop goes through each columnj
. -
DP table update:
- If the current cell
matrix[i][j]
is a'1'
(a character, not the number 1), update the DP table atdp[i + 1][j + 1]
. The reason fori + 1
andj + 1
is to account for the padding; we're essentially shifting the index to ensure the top row and leftmost column in thedp
are all zeros). - The update is done by taking the minimum of the three adjacent cells —
dp[i][j + 1]
,dp[i + 1][j]
, anddp[i][j]
— and adding 1 to it. This represents the side length of the largest square ending atmatrix[i][j]
.
- If the current cell
-
Track the maximum square side: Update the
mx
variable with the maximum value of the currentdp[i + 1][j + 1]
andmx
. This keeps track of the largest square side length found so far. -
Compute final area: After completing the iteration over the entire matrix, the maximum side length of a square with only
1
s is stored inmx
. To find the area, simply returnmx * mx
, which squares the side length to give the area.
Code Analysis:
-
DP table as memoization: The
dp
matrix is a form of memoization that allows the algorithm to refer to previously computed results and build upon them, which dramatically reduces time complexity from exponential to polynomial. -
Time and Space Complexity: The time complexity of this solution is
O(m * n)
since it processes each cell exactly once. The space complexity is alsoO(m * n)
due to the extra DP table used for storing intermediate results.
By applying these steps, the solution leverages dynamic programming to effectively solve the problem in a manageable time frame while ensuring that we do not perform redundant calculations.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach given above. Suppose we have the following binary grid as our input matrix:
1matrix = [ 2 [1, 0, 1, 0, 0], 3 [1, 0, 1, 1, 1], 4 [1, 1, 1, 1, 1], 5 [1, 0, 0, 1, 0] 6]
- Initialization:
We initialize our
dp
table to have dimensions5 x 6
(since the original matrix is4 x 5
, we add one for padding). It looks like this after initialization:
1dp = [ 2 [0, 0, 0, 0, 0, 0], 3 [0, 0, 0, 0, 0, 0], 4 [0, 0, 0, 0, 0, 0], 5 [0, 0, 0, 0, 0, 0], 6 [0, 0, 0, 0, 0, 0] 7]
And we set mx = 0
.
-
Iterate through matrix: We start iterating with
i = 0
andj = 0
. We findmatrix[0][0]
is1
, so we need to updatedp
at[i+1][j+1]
, which isdp[1][1]
. -
DP table update: Since
dp[1][1]
's adjacent cells (dp[0][1]
,dp[1][0]
, anddp[0][0]
) are all zeros, we take the minimum (which is0
) and add1
to it.
1dp = [ 2 [0, 0, 0, 0, 0, 0], 3 [0, 1, 0, 0, 0, 0], // dp[1][1] updated 4 [0, 0, 0, 0, 0, 0], 5 [0, 0, 0, 0, 0, 0], 6 [0, 0, 0, 0, 0, 0] 7]
- Track the maximum square side:
mx
is updated to1
, as1
is larger than0
(previousmx
value).
Continuing in this manner for all 1's in the original matrix:
1Final dp table after iterating through the entire matrix: 2 3dp = [ 4 [0, 0, 0, 0, 0, 0], 5 [0, 1, 0, 1, 0, 0], 6 [0, 1, 0, 1, 1, 1], 7 [0, 1, 1, 1, 2, 2], 8 [0, 1, 0, 0, 1, 0] 9] 10 11Maximum square size found, mx = 2
- Compute final area:
Finally, we compute the area of the largest square found by squaring
mx
. Thus, we get2 * 2 = 4
.
In our example, the largest square composed entirely of 1
s has a side length of 2
, and the area of that square is 4
. The solution correctly identifies this through the methodical updating of the dp
table and maintains the mx
variable as it iterates through the given matrix.
Solution Implementation
1from typing import List
2
3class Solution:
4 def maximalSquare(self, matrix: List[List[str]]) -> int:
5 rows, cols = len(matrix), len(matrix[0]) # Get the dimensions of the matrix
6 dp = [[0] * (cols + 1) for _ in range(rows + 1)] # Initialize DP table with extra row and column
7 max_side_length = 0 # Maximum side length of a square of '1's
8
9 for row in range(rows):
10 for col in range(cols):
11 # Check if the current element is a '1'
12 if matrix[row][col] == '1':
13 # Update the DP table by considering the top, left, and top-left neighbors
14 dp[row + 1][col + 1] = min(
15 dp[row][col + 1], # Top
16 dp[row + 1][col], # Left
17 dp[row][col] # Top-Left
18 ) + 1
19 # Update the max side length found so far
20 max_side_length = max(max_side_length, dp[row + 1][col + 1])
21
22 # Return the area of the largest square
23 return max_side_length * max_side_length
24
1class Solution {
2 public int maximalSquare(char[][] matrix) {
3 // Find the dimensions of the matrix.
4 int rows = matrix.length;
5 int cols = matrix[0].length;
6
7 // Initialize a DP (Dynamic Programming) table with extra row and column.
8 int[][] dp = new int[rows + 1][cols + 1];
9
10 // Initialize the variable to store the size of the maximum square.
11 int maxSquareSize = 0;
12
13 // Loop through each cell in the matrix.
14 for (int i = 0; i < rows; ++i) {
15 for (int j = 0; j < cols; ++j) {
16 // If the cell contains a '1', it is a potential part of a square.
17 if (matrix[i][j] == '1') {
18 // The size of the square ending at (i, j) is 1 plus the minimum of
19 // the size of the squares above, to the left, and diagonally above and to the left.
20 dp[i + 1][j + 1] = Math.min(Math.min(dp[i][j + 1], dp[i + 1][j]), dp[i][j]) + 1;
21
22 // Update the maximum size encountered so far.
23 maxSquareSize = Math.max(maxSquareSize, dp[i + 1][j + 1]);
24 }
25 }
26 }
27
28 // Return the area of the largest square found.
29 return maxSquareSize * maxSquareSize;
30 }
31}
32
1#include <vector>
2#include <algorithm> // for std::min and std::max
3
4class Solution {
5public:
6 int maximalSquare(vector<vector<char>>& matrix) {
7 // Get the number of rows (m) and columns (n) in the matrix.
8 int numRows = matrix.size();
9 int numCols = matrix[0].size();
10
11 // Create a 2D DP (dynamic programming) table with an extra row and column set to 0.
12 vector<vector<int>> dp(numRows + 1, vector<int>(numCols + 1, 0));
13
14 int maxSize = 0; // Initialize the maximum square size found to 0.
15
16 // Iterate through the matrix, starting from the top-left corner.
17 for (int i = 0; i < numRows; ++i) {
18 for (int j = 0; j < numCols; ++j) {
19 // If the current element is '1', calculate the size of the square.
20 if (matrix[i][j] == '1') {
21 // The size of the square ending at (i, j) is the minimum of the three
22 // neighboring squares plus 1.
23 dp[i + 1][j + 1] = std::min(std::min(dp[i][j + 1], dp[i + 1][j]), dp[i][j]) + 1;
24 // Update the maximum size found so far.
25 maxSize = std::max(maxSize, dp[i + 1][j + 1]);
26 }
27 }
28 }
29
30 // Return the area of the largest square found.
31 return maxSize * maxSize;
32 }
33};
34
1function maximalSquare(matrix: string[][]): number {
2 // Get the number of rows (numRows) and columns (numCols) in the matrix.
3 const numRows = matrix.length;
4 const numCols = matrix[0].length;
5
6 // Create a 2D DP (dynamic programming) table with an extra row and column set to 0.
7 let dp: number[][] = Array.from({ length: numRows + 1 }, () => Array(numCols + 1).fill(0));
8
9 let maxSize: number = 0; // Initialize the maximum square size found to 0.
10
11 // Iterate through the matrix, starting from the top-left corner.
12 for (let i = 0; i < numRows; i++) {
13 for (let j = 0; j < numCols; j++) {
14 // If the current element is '1', calculate the size of the square.
15 if (matrix[i][j] === '1') {
16 // The size of the square ending at (i, j) is the minimum of the three
17 // neighboring squares plus 1.
18 dp[i + 1][j + 1] = Math.min(Math.min(dp[i][j + 1], dp[i + 1][j]), dp[i][j]) + 1;
19
20 // Update the maximum size found so far.
21 maxSize = Math.max(maxSize, dp[i + 1][j + 1]);
22 }
23 }
24 }
25
26 // Return the area of the largest square found.
27 return maxSize * maxSize;
28}
29
Time and Space Complexity
The time complexity of the provided code is O(m * n)
, where m
is the number of rows in the matrix and n
is the number of columns. This is because the code contains two nested loops, each of which iterate over the rows and the columns of the input matrix, respectively.
The space complexity of the code is O(m * n)
, since a 2D list dp
of size (m + 1) x (n + 1)
is created to store the size of the largest square ending at each position in the matrix. Each element of the matrix contributes to one cell in the dp
array, hence the space complexity is proportional to the size of the input matrix.
Learn more about how to find time and space complexity quickly using problem constraints.
What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.