Largest Square

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s and return its area.

Example:

Input:

1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0

Dynamic programming with n2 space

We know that to form a square must have a ‘1’ on its top left corner. And for each square of size k, it will also need k – 1 ‘1’ under the top left ‘1’ and k – 1 ‘1’ on the right of the top left ‘1’. Last we need a square of k – 1 ‘1’ on the bottom right.

EG:

1 1 1 1
1 1 1 1  = 1 + 1 1 1    
1 1 1 1    + 
1 1 1 1    1 + 1 1 1
           1   1 1 1
           1   1 1 1

recurrance

We create a 2D DP table and stores the max side length of square whose top left corner is at [i][j]. We will init the bottom row and right most column with 1 if the matrix value is 1 since the square at right most col and bottom row can at most be 1.

So the side length of the max square starting at position [i][j] is

if (matrix[i][j] == '1')
    DP[i][j] = min(DP[i + 1][j], DP[i][j + 1]. DP[i + 1][j + 1])
else
    DP[i][j] = 0

Need to run through the matrix once, so O(mn)

Better DP

Can we shrink the space requirement from O(mn) to O(m) (m > n)

We don’t need to store the whole DP table Since each time we calculate DP[i][j], we will only need 3 values; the right, the bottom, and the bottom right.

For bottom len, we know the first bottom len and will just carry it.

For right len, we need to carry it as well.

For bottom right len, it will just be in right len. So we need one column + one row of memory.

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if(matrix.empty())
            return 0;
        int maxArea = 0;
        int rowLen = matrix.size();
        int colLen = matrix[0].size();
        //topLeftSize stores the side length of square starting at [i][j]
        int maxLen = 0;

        vector<int> bottom(colLen,0);
        vector<int> replace(colLen,0);
        //init bottom row
        for(int i = 0; i < colLen; i ++){
            if(matrix[rowLen - 1][i] == '1'){
                bottom[i] = 1;
                maxLen = 1;
            }

        }
        //init right side
        for(int i = 0; i < rowLen; i ++){
            if(matrix[i][colLen - 1] == '1'){
                maxLen = 1;
            }

        }

        //then iter from bottom right to top left
        int rightPrev = 0;
        for(int i = rowLen - 2; i >= 0; i -- ){
            if(matrix[i][colLen - 1] == '0'){
                rightPrev = 0;

            }
            else{
                rightPrev = 1;
            }
            for(int j = colLen - 2; j >= 0; j --){
                if(matrix[i][j] == '0'){
                    replace[j] = 0;
                    rightPrev = 0;
                }
                else{
                    int rightLen = rightPrev;
                    int bottomLen = bottom[j];
                    int smallSquareLen = bottom[j + 1];
                    replace[j] = min({rightLen, bottomLen, smallSquareLen}) + 1;
                    maxLen = max(replace[j], maxLen);
                    //cout<<"rightLen "<< rightLen <<"bottomLen "<<bottomLen <<"smallSquare "<<smallSquareLen<<'\n';
                    //cout<<"square len at "<< i<< " " <<j<<" with size" <<replace[j] <<"\n";
                    rightPrev = replace[j];
                }
            }

            //bottom.assign(replace.begin(), replace.end()); 
            bottom = replace;
            if (matrix[i][colLen - 1] == '1')
                bottom[colLen - 1] = 1;
            else
                bottom[colLen - 1] = 0;
        }
        return maxLen * maxLen;




        return maxArea;

    }
};

In the code above, we used bottom to record the DP result from the previous row and use replace to remember the DP result of the current row and in the next iteration, we will point bottom to replace.

Bugs

The last col(cell) of bottom

We will not update the last cell of bottom via the nested for loop since it is part of the base case, we need need to update bottom[colLen – 1] at the end of each outer loop iteration.

            bottom = replace;
            if (matrix[i][colLen - 1] == '1')
                bottom[colLen - 1] = 1;
            else
                bottom[colLen - 1] = 0;

We also need to init the preRight at the beginning of each inner for loop to be the right most cell in that row.

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax