# C++ 6ms O(1) space non-DP solution with detailed explanation

• 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

1. 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'`.
2. 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:

``````class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if(matrix.size() == 0 || matrix[0].size() == 0) return 0;
int maxSquare = 0;
for(int i = 0; i < matrix.size(); i++)
for(int j = 0; j < matrix[0].size(); j++)
if(matrix[i][j] != '0') maxSquare = max(maxSquare, findSquare(matrix, i, j));
return maxSquare;
}

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);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.