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


  • 0

    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'-cells and focus on '1'-cells.

    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'-cells. (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'-cells.

    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'-cells.

    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'-cells, 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);
        }
    };
    

Log in to reply
 

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