## Problem:
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 Description
The algorithm maxSolidSquare correctly finds the maximum area of a solid square block in M. It starts off by initializing two arrays, dp0 and dp1, then for each cell, if it is in the first row or column then dp0[i][j] or dp1[i][j] = 1. Else, use the recurrence. Finally, it tracks the maximum value of dp0[i][j] and dp1[i][j] while iterating then returning the square of the maximum value.

fun maxSolidSquare(M[0:m-1][0:n-1]) {
    dp0 = [m][n];
    dp1 = [m][n];
    max = 0;
    
    for (int i=0; i < m-1; i++) {
        for (int j=0; j<n-1; j++) {
            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 = max(max, dp0[i][j], dp1[i][j]);
        }
    }
    return max * max;
}

## Correctness Proof
Goal: maxSolidSquare(M) will return the area of the largest square subarray in which all bits are equal (all 0s or all 1s).

We will prove by induction hypothesis

## Induction Hypothesis
Assume that for all cells up to (i-1,j), (i,j-1), and (i-1,j-1), we have correctly computed the largest solid square side lengths ending there.

## Base Cases
- Both i=0 and j=0 (Empty Array): This will output 0 as there will be no iteration.
- i=0 or j=0: This will output a length of 1 as long as it has a valid 0 or 1.

## Induction Step:
For cell (i,j):
- If M[i][j] == 0: The largest square ending here can only extend a square of 0s if the top, left, and top-left cells also end solid 0. Thus,

- This is the exact same method if it were 1s instead
Thus, the recurrence maintains correctness for all (i,j).

## Time Complexity
For each cell (i,j) is processed once, and each step does O(1) work

### Recurrence:

### Time Complexity:

Given a square matrix m=n: