**Idea:**

`'1'-cell`

: cell in matrix with value `1`

.

`'0'-cell`

: cell in matrix with value `0`

.

A valid square(or just call it square since we only concern valid one) can only ends with `'1'-cell`

, so we will skip all `'0'-cell`

s and focus on `'1'-cell`

s.

Suppose the square ends at a given `'1'-cell`

, denote as `matrix[i][j] = '1'`

, we know it must have a valid square, in worst case is itself, i.e. `square size = 1`

.

Matrix shown as below:

```
0 . . . j
. . . . .
. . . . .
. . . . .
i . . . 1
```

Then we simply expands from `square = 1`

, to see if we can find a larger square ends at `matrix[i][j]`

.

How to expand?

We can expand to `square = 2*2 = 4`

only if

- the cell above it is a
`'1'-cell`

, i.e.`matrix[i-1][j] = '1'`

&& the cell to the left is also a`'1'-cell`

, i.e.`matrix[i][j-1] = '1'`

. - the cells inside the
**new square**of area`4`

are all`'1'-cell`

s. (in that case, only one extra cell -`matrix[i-1][j-1] = '1'`

.)

Matrix shown as below:

```
0 . . . j-1 j
. . . . . .
. . . . . .
. . . . . .
i-1 . . . 1 1
i . . . 1 1
```

Expand fails if

```
0 . . . j-1 j 0 . . . j-1 j 0 . . . j-1 j
. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . .
. . . . . . or . . . . . . or . . . . . .
i-1 . . . 0 1 i-1 . . . 1 0 i-1 . . . 1 1
i . . . 1 1 i . . . 1 1 i . . . 0 1
```

In other words, all the cells surround **current square** must all be `'1'-cell`

s.

If new square of area `4`

is valid, we will try to expand to `square = 3*3 = 9`

, and so on. (Expand both left and above 1 step at a time to ensure it's a square.)

We do it iteratively until we hit the first `'0'-cell`

, and that's the largest square we can get at `matrix[i][j]`

, then just traverse the matrix and get **max** among all the `'1'-cell`

s.

**Complexity:**

The time complexity of finding a max-square for a given `'1'-cell`

should be constant, we will stop if any surrounding cell is a `'0'-cell`

, unless the cells between row(0, i) and column(0, j) are all `'1'-cell`

s, in that case the whole sub-matrix with area `pow(min(i,j),2)`

is a square.

Time complexity: O(mn), runtime 6ms.

Space complexity: O(1).

**Code:**

```
int maximalSquare(vector<vector<char>>& matrix) {
if(matrix.size() == 0 || matrix[0].size() == 0) return 0;
int square = 0;
for(int i = 0; i < matrix.size(); i++)
for(int j = 0; j < matrix[0].size(); j++)
if(matrix[i][j] != '0') square = max(square, findSquare(matrix, i, j));
return square;
}
int findSquare(vector<vector<char>>& matrix, int r, int c){
int row = r-1;
int col = c-1;
while(row >= 0 && col >= 0 && matrix[r][col] == '1' && matrix[row][c] == '1'){
int i = row;
int j = col;
while(i < r && matrix[i][col] == '1') i++;
while(j < c && matrix[row][j] == '1') j++;
if(i != r || j != c) break;
row--;
col--;
}
return pow(r-row,2);
}
```