# naive solution in c++ but 6ms

• ``````class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if(matrix.size() == 0 || matrix[0].size() == 0) return 0;
int h = matrix.size(), w = matrix[0].size();

//vector<vector<bool>> visited(h, vector<bool>(w, false));
int result = 0;
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
int curr = 0;
if(matrix[i][j] == '1'){ //treat it as potential upper left of i
curr++;
int row = i, col = j;
while(helper(matrix, row, col, i, j, h, w)){
row++;
col++;
curr++;
}
}
result = max(result, curr * curr);
}
}
return result;
}
bool helper(vector<vector<char>>& matrix, int row, int col, int i, int j, int h, int w){
if((row+1 < h) && (col+1 < w) && (matrix[row+1][col+1] == '1')){
for(int r = i; r < row+1; r++){
if(matrix[r][col+1] != '1') return false;
}
for(int c = j; c < col+1; c++){
if(matrix[row+1][c] != '1') return false;
}
return true;
}
else return false;
}
};
``````

• use integral image method, should be O(n^2) but 9ms

``````class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
if(matrix.size() == 0 || matrix[0].size() == 0) return 0;
int h = matrix.size(), w = matrix[0].size();

//calculate the accumulative sum
vector<vector<int>> sum(h, vector<int>(w, 0));
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
int n1 = ((i>=1) && (j>=1))? sum[i-1][j-1] : 0;
int n2 = (i>=1)? sum[i-1][j] : 0;
int n3 = (j>=1)? sum[i][j-1] : 0;
sum[i][j] = n2 + n3 - n1 + (int)(matrix[i][j] == '1');
}
}
int result = 0;
for(int i = 0; i < h; i++){
for(int j = 0; j < w; j++){
if(matrix[i][j] == '1'){ //treat it as potential upper left of i
result = max(result, 1);
if((i+result-1 < h) && (j + result-1 < w)){
int n1 = ((i>=1) && (j>=1))? sum[i-1][j-1] : 0;
int n2 = (i>=1)? sum[i-1][j+result-1] : 0;
int n3 = (j>=1)? sum[i+result-1][j-1] : 0;
int range = sum[i+result-1][j+result-1] + n1 - n2 - n3;
if(range == result * result){
int row = i+result-1, col = j+result-1;
while(helper(matrix, row, col, i, j, h, w)){
row++;
col++;
result++;
}
}
}
}
}
}
return result*result;
}
bool helper(vector<vector<char>>& matrix, int row, int col, int i, int j, int h, int w){
if((row+1 < h) && (col+1 < w) && (matrix[row+1][col+1] == '1')){
for(int r = i; r < row+1; r++){
if(matrix[r][col+1] != '1') return false;
}
for(int c = j; c < col+1; c++){
if(matrix[row+1][c] != '1') return false;
}
return true;
}
else return false;
}
};
``````

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