Largest Square of 1s in a Binary Matrix

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.

For example:

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

In the above example, the function should return 4 because the largest square containing only 1's has a side length of 2. The area of the square is therefore 2 * 2 = 4.

Here are a few other test cases to consider:

1. A matrix with all 0s.
2. A matrix with a single 1.
3. A rectangular matrix.
4. An empty matrix.

Write a function that efficiently computes the largest square area given an input binary matrix. Explain the time and space complexity of your solution.

## Largest Square of 1s in a Binary Matrix

This problem asks us to find the largest square submatrix containing only 1s within a given binary matrix. We can approach this problem using dynamic programming to efficiently compute the size of the largest square ending at each cell.

### 1. Naive (Brute Force) Solution

We can iterate through each cell of the matrix and, for each cell containing a '1', we can try to expand a square with that cell as the top-left corner. We keep expanding the square until we encounter a '0' or reach the boundary of the matrix. The time complexity for this approach would be high.

### 2. Optimal (Dynamic Programming) Solution

The dynamic programming approach is more efficient. We create a DP table of the same dimensions as the input matrix. Each cell `dp[i][j]` in the DP table stores the side length of the largest square of 1s ending at `matrix[i][j]`. The value of `dp[i][j]` depends on its neighbors `dp[i-1][j]`, `dp[i][j-1]`, and `dp[i-1][j-1]`.

Here's the algorithm:

1.  Initialize a DP table `dp` with the same dimensions as the input matrix, filled with 0s.
2.  Iterate through the input `matrix` from top-left to bottom-right.
3.  If `matrix[i][j]` is '1':
    *   `dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1`
4.  Keep track of the maximum value in the `dp` table, which represents the side length of the largest square.
5.  Return the square of the maximum side length.

```python
def maximal_square(matrix):
    if not matrix:
        return 0

    rows, cols = len(matrix), len(matrix[0])
    dp = [[0] * cols for _ in range(rows)]
    max_side = 0

    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == '1':
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                max_side = max(max_side, dp[i][j])

    return max_side * max_side

# Example usage:
matrix1 = [["1","0","1","0","0"],
           ["1","0","1","1","1"],
           ["1","1","1","1","1"],
           ["1","0","0","1","0"]]
print(f"Largest square area: {maximal_square(matrix1)}")  # Output: 4

matrix2 = [["0","1"],
           ["1","0"]]
print(f"Largest square area: {maximal_square(matrix2)}")  # Output: 1

matrix3 = [["0"]]
print(f"Largest square area: {maximal_square(matrix3)}")  # Output: 0

3. Big(O) Runtime Analysis

• The algorithm iterates through each cell of the m x n matrix once.
• For each cell, it performs a constant number of operations (min and addition).
• Therefore, the time complexity is O(m * n), where m is the number of rows and n is the number of columns in the matrix.

4. Big(O) Space Usage Analysis

• The algorithm uses a DP table of the same dimensions as the input matrix.
• Thus, the space complexity is O(m * n), where m is the number of rows and n is the number of columns in the matrix.

5. Edge Cases

1. Empty Matrix:
   • If the input matrix is empty (i.e., has 0 rows or 0 columns), the function should return 0 because there can be no square.
2. Matrix with No 1s:
   • If the matrix contains only 0s, the function should return 0 because there can be no square of 1s.
3. Matrix with a Single 1:
   • If the matrix contains only a single 1, the function should return 1, as the largest square will have a side length of 1.
4. Rectangular Matrix:
   • The algorithm should correctly handle rectangular matrices (i.e., matrices where the number of rows is not equal to the number of columns).
5. Non-Binary Matrix:
   • The prompt specified a binary matrix but if the matrix contains values other than "0" or "1", we can modify the code to accommodate other values or raise an exception if those are encountered. However, for the purpose of this prompt, we assume input validity.