# 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

Table of Contents

# 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.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.

Posted on Categories Leetcode