# Integral image solution, 156ms. I know I know, it's slow, just want to throw it out here

• Just want to throw a solution using integral image. Clearly it's not as fast as DP solution, but it's fun

``````class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int rows = matrix.size();
if (rows == 0) return 0;
int cols = matrix[0].size();
if (cols == 0) return 0;
int val;
vector<vector<int> > image(rows+1, vector<int>(cols+1, 0)); // Integral image
for (int r = 1; r <= rows; r++){
for (int c = 1; c <= cols; c++){
val = (matrix[r-1][c-1] == '0' ? 0 : 1);
image[r][c] = val + image[r][c-1] + image[r-1][c] - image[r-1][c-1];
}
}
if (image[rows][cols] == 0) return 0;
int maxSize = 1;
for (int r = 0; r <= rows; r++){
for (int c = 0; c <= cols; c++){
for (int s = min(rows-r, cols-c); s >= maxSize; s--){
if (image[r+s][c+s] + image[r][c] - image[r][c+s] - image[r+s][c] == s * s) {
maxSize = s;
break;
}
}
}
}
return maxSize * maxSize;
}
};``````

• Your idea is good but the code needs optimization.

After generating the summed area table, we can scan the table row by row, checking if there is any square satisfying the square area condition. Once we found one, we can increase the maxSize by 1 and check next row. The optimized version has running time of 12 ms.

``````class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int rows = matrix.size();
if (rows == 0) return 0;
int cols = matrix[0].size();
if (cols == 0) return 0;
int val;
vector < vector<int> > image(rows+1, vector <int> (cols+1, 0)); // Integral image
for (int r = 1; r <= rows; r++) {
for (int c = 1; c <= cols; c++) {
val = (matrix[r-1][c-1] == '0' ? 0 : 1);
image[r][c] = val + image[r][c-1] + image[r-1][c] - image[r-1][c-1];
}
}
if (image[rows][cols] == 0) return 0;
int maxSize = 1;
for (int r = 2; r <= rows; r++){
int next = maxSize + 1;
int area = next*next;
for (int c = next; c <= cols; c++){
if (image[r][c] + image[r-next][c-next] - image[r][c-next] - image[r-next][c] == area) {
maxSize = next;
break;
}
}
}
return maxSize * maxSize;
}
};
``````

And the Python version:

``````class Solution(object):
def maximalSquare(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
rows, max_size = len(matrix), 0
if rows > 0:
cols = len(matrix[0])
'''
Use summed area table to calculate maximal square
The value at image[x][y] is the sum of all elements above and to the left of (x-1, y-1) in matrix (converted to int)
The area of rectangle ABDC (top left -> top right -> bottom right --> bottom left), as below
A   B
C   D
is image[D] + image[A] - image[B] - image[C]
We can scan the summed area table, check if the area of a squre is exactly the square of the length of edge
'''
image = [[0] * (cols+1) for _ in range(rows+1)]
# generate summed-area table
for x in xrange(rows):
for y in xrange(cols):
image[x+1][y+1] = image[x+1][y] + image[x][y+1] - image[x][y] + (1 if matrix[x][y] == '1' else 0)

if image[rows][cols] > 0:
max_size = 1
for x in xrange(2, rows+1):
# next_size: next possible maximal size of square
next_size = max_size + 1
area = next_size*next_size
for y in xrange(next_size, cols+1):
# check the area of squares
if (image[x][y] + image[x-next_size][y-next_size] - image[x][y-next_size] - image[x-next_size][y] == area):
max_size = next_size
break;

return max_size*max_size
``````

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