221. Maximal Square

Problem Description

The problem presents a scenario where you are given a matrix composed of only 0s and 1s, which corresponds to a binary grid. Your objective is to discover the largest square formed entirely of 1s 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 1s, 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 1s 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 with m + 1 rows and n + 1 columns filled with zeros, where m and n are the row and column counts of the input matrix, respectively. Also, initialize a variable mx 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 row i, and the inner loop goes through each column j.
DP table update:
- If the current cell matrix[i][j] is a '1' (a character, not the number 1), update the DP table at dp[i + 1][j + 1]. The reason for i + 1 and j + 1 is to account for the padding; we're essentially shifting the index to ensure the top row and leftmost column in the dp are all zeros).
- The update is done by taking the minimum of the three adjacent cells — dp[i][j + 1], dp[i + 1][j], and dp[i][j] — and adding 1 to it. This represents the side length of the largest square ending at matrix[i][j].
Track the maximum square side: Update the mx variable with the maximum value of the current dp[i + 1][j + 1] and mx. 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 1s is stored in mx. To find the area, simply return mx * 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 also O(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 Evaluator

Example 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:

matrix = [
  [1, 0, 1, 0, 0],
  [1, 0, 1, 1, 1],
  [1, 1, 1, 1, 1],
  [1, 0, 0, 1, 0]
]

Initialization: We initialize our dp table to have dimensions 5 x 6 (since the original matrix is 4 x 5, we add one for padding). It looks like this after initialization:

dp = [
  [0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0]
]

And we set mx = 0.

Iterate through matrix: We start iterating with i = 0 and j = 0. We find matrix[0][0] is 1, so we need to update dp at [i+1][j+1], which is dp[1][1].
DP table update: Since dp[1][1]'s adjacent cells (dp[0][1], dp[1][0], and dp[0][0]) are all zeros, we take the minimum (which is 0) and add 1 to it.

dp = [
  [0, 0, 0, 0, 0, 0],
  [0, 1, 0, 0, 0, 0], // dp[1][1] updated
  [0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0]
]

Track the maximum square side: mx is updated to 1, as 1 is larger than 0 (previous mx value).

Continuing in this manner for all 1's in the original matrix:

Final dp table after iterating through the entire matrix:

dp = [
  [0, 0, 0, 0, 0, 0],
  [0, 1, 0, 1, 0, 0],
  [0, 1, 0, 1, 1, 1],
  [0, 1, 1, 1, 2, 2],
  [0, 1, 0, 0, 1, 0]
]

Maximum square size found, mx = 2

Compute final area: Finally, we compute the area of the largest square found by squaring mx. Thus, we get 2 * 2 = 4.

In our example, the largest square composed entirely of 1s 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

How does merge sort divide the problem into subproblems?

Divide the array into two equal halves by index

Divide the array into two based on whether an element is smaller than an arbitrary value

Divide the array into a stray element and the rest of the array

Merge sort does not use divide and conquer

I don’t know