221. Maximal Square - Detailed Explanation

Brute Force Java Implementation:
Below is a Java implementation of the brute force method. It uses a loop to expand the square size and only checks the newly added row and column at each step (to avoid re-checking the entire square from scratch every time). This optimization improves the constant factors but the worst-case order of growth is still the same.

Complexity Analysis: The brute force approach runs in O( (m \times n)^2 ) time in the worst case. If the matrix is mostly filled with 1's, we end up checking many possible squares for each starting position. For a 300x300 matrix (worst-case dimensions per constraints), this approach could involve on the order of billions of cell checks, which is highly inefficient. The space complexity is O(1) extra since we only use a few loop variables and flags.

Space Optimization: The above DP solution uses a 2D table of the same size as the input matrix. We can optimize this because to compute dp[i][j], we only need the values from the previous row (i-1) and the current row (i) as we build it up, not the entire table. One common optimization is to use a one-dimensional array that keeps track of the current row's DP values and update it as we move along, using an additional variable to store the value from the previous row (the diagonal-up value) . This reduces space complexity to O(n). However, the implementation is a bit trickier (you have to be careful to update in the correct order and use a temporary variable for the diagonal value). For clarity, the 2D approach above is easier to understand, but in a real interview or competition, you might mention this optimization if asked about space usage.

Complexity Analysis: The dynamic programming approach runs in O(m * n) time and uses O(m * n) space in the basic implementation . Given the problem constraints, a 300x300 matrix would require at most 90,000 operations, which is very efficient. The optimized space version runs in O(m * n) time and O(n) space. In practical terms, both will run quickly for the given input size. This is a huge improvement over the brute force method.

Step-by-Step Walkthrough

Let's walk through an example to see how the dynamic programming solution works in detail. Consider Example 1's matrix:

matrix = 
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

We will construct the dp table that represents the largest square ending at each position. Initially, we start with all zeros in dp. We iterate through each cell:

• Row 0:

  • matrix[0][0] = 1 ⇒ this is the first row/col, so dp[0][0] = 1.
  • matrix[0][1] = 0 ⇒ dp[0][1] = 0 (no square can end at a 0).
  • matrix[0][2] = 1 ⇒ first row, so dp[0][2] = 1.
  • matrix[0][3] = 0 ⇒ dp[0][3] = 0.
  • matrix[0][4] = 0 ⇒ dp[0][4] = 0.
    After first row, dp[0] looks like: [1, 0, 1, 0, 0] and current max square side = 1.

• Row 1:

  • matrix[1][0] = 1 ⇒ first column, so dp[1][0] = 1.
  • matrix[1][1] = 0 ⇒ dp[1][1] = 0.
  • matrix[1][2] = 1 ⇒ neighbors (up: dp[0][2]=1, left: dp[1][1]=0, up-left: dp[0][1]=0) have a minimum of 0, so dp[1][2] = 0 + 1 = 1.
  • matrix[1][3] = 1 ⇒ neighbors (up: dp[0][3]=0, left: dp[1][2]=1, up-left: dp[0][2]=1) min is 0, so dp[1][3] = 0 + 1 = 1.
  • matrix[1][4] = 1 ⇒ neighbors (up: dp[0][4]=0, left: dp[1][3]=1, up-left: dp[0][3]=0) min is 0, so dp[1][4] = 0 + 1 = 1.
    After second row, dp[1] is: [1, 0, 1, 1, 1] (max side still 1 so far).

• Row 2:

  • matrix[2][0] = 1 ⇒ first column, dp[2][0] = 1.
  • matrix[2][1] = 1 ⇒ neighbors (up: dp[1][1]=0, left: dp[2][0]=1, up-left: dp[1][0]=1) min is 0, so dp[2][1] = 0 + 1 = 1.
  • matrix[2][2] = 1 ⇒ neighbors (up: dp[1][2]=1, left: dp[2][1]=1, up-left: dp[1][1]=0) min is 0, so dp[2][2] = 0 + 1 = 1.
  • matrix[2][3] = 1 ⇒ neighbors (up: dp[1][3]=1, left: dp[2][2]=1, up-left: dp[1][2]=1) min is 1, so dp[2][3] = 1 + 1 = 2. Now we found a square of side 2 ending at cell (2,3).
  • matrix[2][4] = 1 ⇒ neighbors (up: dp[1][4]=1, left: dp[2][3]=2, up-left: dp[1][3]=1) min is 1, so dp[2][4] = 1 + 1 = 2. Another square of side 2 ends at (2,4).
    After third row, dp[2] is: [1, 1, 1, 2, 2]. The max square side length is now 2.

• Row 3:

  • matrix[3][0] = 1 ⇒ first column, dp[3][0] = 1.
  • matrix[3][1] = 0 ⇒ dp[3][1] = 0.
  • matrix[3][2] = 0 ⇒ dp[3][2] = 0.
  • matrix[3][3] = 1 ⇒ neighbors (up: dp[2][3]=2, left: dp[3][2]=0, up-left: dp[2][2]=1) min is 0 (left neighbor is 0), so dp[3][3] = 0 + 1 = 1.
  • matrix[3][4] = 0 ⇒ dp[3][4] = 0.
    Fourth row dp[3]: [1, 0, 0, 1, 0]. Max side remains 2.

The final DP table (each entry representing the largest square side ending at that cell) looks like:

dp =
1 0 1 0 0
1 0 1 1 1
1 1 1 2 2
1 0 0 1 0

From this table, we see the largest value is 2, which corresponds to a 2x2 square of 1's. Squaring that gives area = 4, which matches the expected output. The cells with value 2 in the DP table indicate the bottom-right corners of the largest squares. Visual representation of Example 1: the red and green outlines highlight two possible largest 2x2 squares of 1's in the matrix. Each has area 4, which is the maximal square area for this matrix.

The dynamic programming approach efficiently computes these values in one pass through the matrix. Notice how each dp cell was computed using the three neighboring dp values, which were themselves computed earlier (since we go row by row). This overlapping of subproblems is what makes the DP solution much faster than brute force – we never re-check a region of the matrix more than once. Each cell's contribution is recorded and reused.

Common Mistakes & Edge Cases

Common Pitfalls:

• Forgetting to square the result: The question asks for the area of the largest square, not the side length. A common mistake is to return the side length by accident. Make sure to return maxSide * maxSide at the end.

• Off-by-one errors in DP indices: When implementing the DP solution, be careful with indices, especially if you use a padded DP array or if you update in place. It's easy to mix up dp[i-1][j] vs dp[i][j-1] or go out of bounds. A typical trick is to create a DP table of size (m+1) x (n+1) with an extra top row and left column of zeros to avoid having to do boundary checks on each. If you do this, remember that your dp indices are offset by one from the matrix indices.

• Wrong data type comparisons: In many languages (like Java and Python on LeetCode), the matrix is given as a grid of characters '0' and '1' (not integers 0 and 1). Ensure you compare them as characters or convert to int appropriately. For example, in Java, use matrix[i][j] == '1' not == 1. In Python, if the input is a list of strings, you might be comparing string characters. This mistake can lead to logic errors or always false comparison.

• Not initializing the answer correctly: If the matrix has no 1 at all, the largest square area should be 0. Make sure your algorithm handles the case where you never find any 1's. In our DP solution, maxSide stays 0 if no 1 is found, and we return 0 (which is correct). In the brute force approach, we initialized maxSide = 0 and only update it when a 1 is found, so it also correctly returns 0 for an all-zero matrix. Just double-check that you cover this edge case.

• Not handling single row or single column matrices: The solution logic actually covers these implicitly, but it's worth noting. If m=1 or n=1, the answer is simply whether there's a 1 in the matrix (area will be 1 if yes, or 0 if no). Our DP handles this because it sets dp[i][j]=1 for any '1' in first row/col. Just be careful not to run min() on neighbors that don't exist. The code above checks i==0 or j==0 to handle edges.

Edge Cases to test:

• All zeros matrix (e.g. [[0,0],[0,0]]) -> output 0.
• Matrix with all ones (e.g. a 5x5 of all 1's) -> output would be $5^2 = 25` (the whole matrix is the square).
• Rectangular matrix (where m \neq n). For example, a 1x5 matrix of 1's should output 1 (since only 1x1 squares can fit in one row). A 3x5 matrix of all 1's should output $3^2=9` (limited by the smaller dimension = 3).
• A matrix with one large square of 1's surrounded by 0's, versus a matrix with several smaller disjoint squares of 1's. Make sure the algorithm indeed finds the largest one.
• Single cell matrix: [[ "1" ]] should return 1; [[ "0" ]] returns 0 (covered by Example 3).

Alternative Variations & Related Problems

This problem of finding a largest all-1 square is a classic dynamic programming scenario. There are a few variations and related problems you might want to explore for further practice:

• Maximal Rectangle (LeetCode #85, Hard): Instead of the largest square, find the largest rectangle containing only 1's in a binary matrix. This problem is more challenging because the rectangle doesn't have to be a square. It can often be solved by using a histogram approach on each row (treating consecutive 1's in columns as heights). The dynamic programming strategy for squares doesn't directly apply, but it's a related concept.

• Count Square Submatrices with All Ones (LeetCode #1277, Medium): Rather than just the largest square, this variation asks you to count all square submatrices in the matrix that are filled with 1's. It turns out you can use a very similar DP approach to this problem – in fact, you can reuse the dp table logic from Maximal Square and sum up all the values in the table (because each dp[i][j] value represents the side length of a square, so it contributes that many squares of smaller size.

• Largest Plus Sign (LeetCode #764, Medium): Find the largest "plus" shape (cross of 1's) in a grid. This is a different shape (not a square), but it also uses dynamic programming from four directions to compute the longest arms of consecutive 1's at each. It’s a twist on finding contiguous 1's in different orientations.

• Maximal Square II (Variation): A twist on the maximal square problem where you are allowed to have at most one 0 inside the square. In other words, find the largest square submatrix that contains almost all 1's except for at most one cell. This is a more advanced variation that would require modifying the DP state to account for the one allowed (it becomes a 3D DP or a two-layer DP: one for squares with no zeros, one for squares with one zero).