# Maximal Square
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximal-square)
Canonical: https://scaleengineer.com/dsa/problems/maximal-square
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Matrix
**Companies:** [Airbnb](https://scaleengineer.com/companies/airbnb), [ByteDance](https://scaleengineer.com/companies/bytedance), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [Karat](https://scaleengineer.com/companies/karat), [Myntra](https://scaleengineer.com/companies/myntra), [Nvidia](https://scaleengineer.com/companies/nvidia), [Oracle](https://scaleengineer.com/companies/oracle), [PayPal](https://scaleengineer.com/companies/paypal), [SAP](https://scaleengineer.com/companies/sap), [ServiceNow](https://scaleengineer.com/companies/servicenow), [Walmart Labs](https://scaleengineer.com/companies/walmart-labs), [Wise](https://scaleengineer.com/companies/wise), [eBay](https://scaleengineer.com/companies/ebay), [Salesforce](https://scaleengineer.com/companies/salesforce), [Citadel](https://scaleengineer.com/companies/citadel), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [PhonePe](https://scaleengineer.com/companies/phonepe), [Booking.com](https://scaleengineer.com/companies/booking.com), [BharatPe](https://scaleengineer.com/companies/bharatpe), [GSA Capital](https://scaleengineer.com/companies/gsa-capital)
---
## Problem
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:**

![](https://assets.glich.co/dsa/maximal-square/image0.jpg) 

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

![](https://assets.glich.co/dsa/maximal-square/image1.jpg) 

**Input:** matrix = [["0","1"],["1","0"]]
**Output:** 1

**Example 3:**

**Input:** matrix = [["0"]]
**Output:** 0

**Constraints:**

* `m == matrix.length`
* `n == matrix[i].length`
* `1 <= m, n <= 300`
* `matrix[i][j]` is `'0'` or `'1'`.

# Approaches
## Brute Force Approach
Check every possible square in the matrix by iterating through each cell as a potential top-left corner of a square and expanding the size until we find the largest valid square.
**Time:** O(m*n*min(m,n)^2) where m and n are the dimensions of the matrix. For each cell, we might need to check up to min(m,n) cells in both directions. · **Space:** O(1) as we only use a constant amount of extra space
**Pros:** Simple to understand and implement; No extra space required except for a few variables
**Cons:** Very inefficient for large matrices; Performs redundant checks on the same cells multiple times; Time complexity is cubic in the worst case
### Explanation
For each cell in the matrix that contains '1', we try to expand it into a square by checking if all cells within the potential square are '1's. We keep track of the maximum square size found.

```java
class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0) return 0;
        
        int rows = matrix.length;
        int cols = matrix[0].length;
        int maxSquareLen = 0;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    int squareLen = 1;
                    boolean flag = true;
                    
                    // Try to expand the square while staying within bounds
                    while (i + squareLen < rows && j + squareLen < cols && flag) {
                        // Check the new row and column to be added
                        for (int k = j; k <= j + squareLen; k++) {
                            if (matrix[i + squareLen][k] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        
                        for (int k = i; k <= i + squareLen; k++) {
                            if (matrix[k][j + squareLen] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        
                        if (flag) squareLen++;
                    }
                    
                    maxSquareLen = Math.max(maxSquareLen, squareLen);
                }
            }
        }
        
        return maxSquareLen * maxSquareLen;
    }
}
```
### Algorithm
1. Iterate through each cell in the matrix
2. If a cell contains '1', try to expand it into a square
3. For each expansion:
   - Check if all cells in the new row and column are '1's
   - If yes, continue expanding
   - If no, stop and update maximum square length if necessary
4. Return the area of the largest square found

## Dynamic Programming Approach
Use dynamic programming to build the solution by maintaining a dp table where dp[i][j] represents the side length of the largest square ending at position (i,j).
**Time:** O(m*n) where m and n are the dimensions of the matrix. We only need to visit each cell once. · **Space:** O(m*n) to store the dp table
**Pros:** Much more efficient than brute force approach; Avoids redundant calculations; Solves the problem in a single pass through the matrix
**Cons:** Requires additional space for the dp table; May not be optimal for very sparse matrices with few 1's
### Explanation
We create a dp table where dp[i][j] represents the side length of the largest square that can be formed with (i,j) as the bottom-right corner. The value at each position depends on the minimum of the values at the top, left, and top-left positions plus 1.

```java
class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0) return 0;
        
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] dp = new int[rows + 1][cols + 1];
        int maxSquareLen = 0;
        
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (matrix[i-1][j-1] == '1') {
                    dp[i][j] = Math.min(
                        Math.min(dp[i-1][j], dp[i][j-1]),
                        dp[i-1][j-1]
                    ) + 1;
                    maxSquareLen = Math.max(maxSquareLen, dp[i][j]);
                }
            }
        }
        
        return maxSquareLen * maxSquareLen;
    }
}
```
### Algorithm
1. Create a dp table with dimensions (m+1) x (n+1)
2. For each cell (i,j) in the original matrix:
   - If the cell contains '1', set dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
   - If the cell contains '0', dp[i][j] remains 0
3. Keep track of the maximum value in dp table
4. Return the square of the maximum value

## Space-Optimized Dynamic Programming
Optimize the space usage of the dynamic programming approach by using only a 1D array instead of a 2D matrix, since we only need the previous row's values.
**Time:** O(m*n) where m and n are the dimensions of the matrix · **Space:** O(n) where n is the number of columns in the matrix
**Pros:** Most space-efficient approach; Same time complexity as regular dynamic programming; Better cache performance due to smaller memory footprint
**Cons:** Slightly more complex to understand and implement; Still requires O(n) extra space
### Explanation
We can optimize the space usage by observing that we only need the previous row's values and the previous column's value to calculate the current cell. We can use a 1D array and keep track of the previous diagonal value separately.

```java
class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0) return 0;
        
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[] dp = new int[cols + 1];
        int maxSquareLen = 0;
        int prev = 0;
        
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                int temp = dp[j];
                if (matrix[i-1][j-1] == '1') {
                    dp[j] = Math.min(Math.min(dp[j], dp[j-1]), prev) + 1;
                    maxSquareLen = Math.max(maxSquareLen, dp[j]);
                } else {
                    dp[j] = 0;
                }
                prev = temp;
            }
        }
        
        return maxSquareLen * maxSquareLen;
    }
}
```
### Algorithm
1. Create a 1D dp array of length n+1
2. For each cell in the matrix:
   - Store the previous diagonal value
   - If current cell is '1', update dp[j] using the minimum of previous values
   - If current cell is '0', set dp[j] to 0
   - Update the previous diagonal value for next iteration
3. Keep track of maximum value seen
4. Return the square of the maximum value

# Solutions
### CSharp

```csharp
public class Solution {
    public int MaximalSquare(char[][] matrix) {
        int m = matrix.Length, n = matrix[0].Length;
        var dp = new int[m + 1, n + 1];
        int mx = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '1') {
                    dp[i + 1, j + 1] = Math.Min(Math.Min(dp[i, j + 1], dp[i + 1, j]), dp[i, j]) + 1;
                    mx = Math.Max(mx, dp[i + 1, j + 1]);
                }
            }
        }
        return mx * mx;
    }
}
```

### Java

```java
class Solution {
public
  int maximalSquare(char[][] matrix) {
    int m = matrix.length, n = matrix[0].length;
    int[][] dp = new int[m + 1][n + 1];
    int mx = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (matrix[i][j] == '1') {
          dp[i + 1][j + 1] =
              Math.min(Math.min(dp[i][j + 1], dp[i + 1][j]), dp[i][j]) + 1;
          mx = Math.max(mx, dp[i + 1][j + 1]);
        }
      }
    }
    return mx * mx;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maximalSquare(vector<vector<char>> &matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    int mx = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (matrix[i][j] == '1') {
          dp[i + 1][j + 1] = min(min(dp[i][j + 1], dp[i + 1][j]), dp[i][j]) + 1;
          mx = max(mx, dp[i + 1][j + 1]);
        }
      }
    }
    return mx * mx;
  }
};

```

### Python

```python
''' eg. a 10*10 sqaure with full of 1s this square move 1 line down this square move 1 line right so there needs an extra single 1 at bottom right, to make it a larger full square ''' class Solution : def maximalSquare ( self , matrix : List [ List [ str ]]) -> int : m , n = len ( matrix ), len ( matrix [ 0 ]) dp = [[ 0 ] * ( n + 1 ) for _ in range ( m + 1 )] mx = 0 for i in range ( m ): for j in range ( n ): if matrix [ i ][ j ] == '1' : dp [ i + 1 ][ j + 1 ] = 1 + min ( dp [ i ][ j + 1 ], dp [ i + 1 ][ j ], dp [ i ][ j ]) mx = max ( mx , dp [ i + 1 ][ j + 1 ]) return mx * mx
```