Maximal Square

Problem Statement
You are given a 2D binary matrix filled with '0's and '1's.
Your task is to find the largest square containing only '1's and return its area.

Example
Input:

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

Output:
4
Explanation: The largest square containing only '1's has a side length of 2, so its area = 2 × 2 = 4.

Understanding the Problem

We have a grid of '0's and '1's.
We want to find the largest square of '1's that can be formed inside the grid.

For example:

In the given matrix, there are multiple '1's, but only some of them can form a complete square.
The key idea is to check whether a '1' at position (i, j) can extend a smaller square that ends just above or to its left.

If we know the size of the largest square ending at (i-1, j), (i, j-1), and (i-1, j-1), we can use that to find the size of the square ending at (i, j).

Thinking Process and Approach

We can use Dynamic Programming (DP) to solve this efficiently.

Create a 2D DP array dp where dp[i][j] represents the side length of the largest square that ends at cell (i, j).
If matrix[i][j] == '0', then it cannot be part of any square, so dp[i][j] = 0.
If matrix[i][j] == '1', then the value depends on its neighbors: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) This means the current cell can form a square only if all three neighboring positions can form a smaller square.
Keep track of the maximum side length found during the process.
Finally, return the square of that side length (since area = side × side).

Step-by-Step Example

Let’s take a smaller matrix:

1 0 1 0
1 1 1 1
1 1 1 1

We fill the DP table as follows:

i\j	0	1	2	3
0	1	0	1	0
1	1	1	1	1
2	1	2	2	2

Here’s how it’s calculated:

For dp[2][1], since matrix[2][1] = 1,
dp[2][1] = 1 + min(dp[1][1], dp[2][0], dp[1][0]) = 1 + min(1,1,1) = 2
For dp[2][2],
dp[2][2] = 1 + min(dp[1][2], dp[2][1], dp[1][1]) = 1 + min(1,2,1) = 2

The largest square side = 2 → area = 4.

Java Code Implementation

public class MaximalSquare {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int rows = matrix.length;
        int cols = matrix[0].length;
        int maxSide = 0;

        int[][] dp = new int[rows + 1][cols + 1];

        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (matrix[i - 1][j - 1] == '1') {
                    dp[i][j] = 1 + Math.min(
                        Math.min(dp[i - 1][j], dp[i][j - 1]),
                        dp[i - 1][j - 1]
                    );
                    maxSide = Math.max(maxSide, dp[i][j]);
                }
            }
        }

        return maxSide * maxSide;
    }
}

Thinking Behind the Code

We add an extra row and column (dp[rows+1][cols+1]) to simplify boundary checks.
When we find '1' in the matrix, we calculate how big a square can be formed ending at that cell.
The min() function ensures that the square extends only as far as all adjacent squares allow.
We keep updating maxSide during the iteration.
Finally, we return maxSide * maxSide as the area.

Time and Space Complexity

Time Complexity: O(m × n)
We process every cell once.
Space Complexity: O(m × n)
We use an auxiliary DP table of the same size as the matrix.

We can further reduce space to O(n) by using only one row of DP at a time, since each row depends only on the previous one.

Key Takeaways

This problem uses Dynamic Programming to extend smaller squares into larger ones.
The crucial relation is
dp[i][j] = 1 + min(top, left, top-left).
Instead of brute-force searching all squares, we compute results incrementally.
Understanding how smaller subproblems (smaller squares) combine helps build intuition for many 2D