# **Maximum Area of Solid Square Blocks**
Suppose you are given an m by n bitmap as an array M[0:m][0:n] of 0s and 1s. A solid block in M is a subarray of the form M[i:i'][j:j'] in which all bits are equal. A solid block is square if it has the same number of rows and columns.

Describe an algorithm to find the maximum area of a solid square block in M in O(n^2) time using dynamic programming.

# **Algorithm**
The following algorithm finds the largest square of identical bits in a binary matrix. The function maxSolidSquare creates two helper matrices (dp0 and dp1), with each cell storing the size of the largest solid square ending that the current position. The value of each cell is determined by checking its neighbors. The max side length is then used to find and return the area of the largest solid square block.

fun maxSolidSquare(M[0:m-1][0:n-1]) {

    var dp0 = make2D(m, n, 0);
    var dp1 = make2D(m, n, 0);
    var max_val = 0;
    
    for (var i = 0; i < m; i = i + 1) {
        for (var j = 0; j < n; j = j + 1) {
            
            if (M[i][j] == 0) {
                if (i == 0 or j == 0) {
                    dp0[i][j] = 1;
                }
                else {
                    dp0[i][j] = 1 + min(dp0[i-1][j], dp0[i][j-1], dp0[i-1][j-1]);
                }
                dp1[i][j] = 0;
            }
            else {
                if (i == 0 or j == 0) {
                    dp1[i][j] = 1;
                }
                else {
                    dp1[i][j] = 1 + min(dp1[i-1][j], dp1[i][j-1], dp1[i-1][j-1]);
                }
                dp0[i][j] = 0;
            }

            max_val = max(max_val, dp0[i][j], dp1[i][j]);
        }
    }
    
    return max_val * max_val;
}

# **Correctness Proof**

Goal: the function maxSolidSquare will find and return the area of the largest solid square block in which all bits are identical

Base Case:
* both i = 0 and j = 0: the function will return 0, there will be no iteration
* i = 0 OR j = 0: the function will return a length of 1 (because one cell with a 0 or 1 will return one 1x1 square)

Induction Step:
For any cell (i,j):
* if M[i][j] == 0: the largest square can only extend a square of 0s if the top, left, and top-left cells also end solid 0 --> ```dp0[i][j] = 1 + min(dp0[i-1][j], dp0[i][j-1], dp0[i-1][j-1])```
* same logic applies in the case of 1s instead of 0s, using the dp1 table

Thus, by induction, the algorithm correctly computes and returns the side length of the largest solid square in M.
# **Time Complexity**
For each cell (i, j) is processed one time --> O(1) work

**Recurrence** --> ```T(i,j - 1) + O(1)```

**Time Complexity**