221. Maximal Square

  • 27.8%

https://leetcode.com/problems/maximal-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.

1
2
3
4
5
6
7
For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.

需要思考


https://discuss.leetcode.com/topic/15328/easy-dp-solution-in-c-with-detailed-explanations-8ms-o-n-2-time-and-o-n-space

Easy DP solution in C++ with detailed explanations (8ms, O(n^2) time and O(n) space)

Well, this problem desires for the use of dynamic programming. They key to any DP problem is to come up with the state equation. In this problem, we define the state to be the maximal size of the square that can be achieved at point (i, j), denoted as P[i][j]. Remember that we use size instead of square as the state (square = size^2).

Now let’s try to come up with the formula for P[i][j].

First, it is obvious that for the topmost row (i = 0) and the leftmost column (j = 0), P[i][j] = matrix[i][j]. This is easily understood. Let’s suppose that the topmost row of matrix is like [1, 0, 0, 1]. Then we can immediately know that the first and last point can be a square of size 1 while the two middle points cannot make any square, giving a size of 0. Thus, P = [1, 0, 0, 1], which is the same as matrix. The case is similar for the leftmost column. Till now, the boundary conditions of this DP problem are solved.

Let’s move to the more general case for P[i][j] in which i > 0 and j > 0. First of all, let’s see another simple case in which matrix[i][j] = 0. It is obvious that P[i][j] = 0 too. Why? Well, since matrix[i][j] = 0, no square will contain matrix[i][j]. According to our definition of P[i][j], P[i][j] is also 0.

Now we are almost done. The only unsolved case is matrix[i][j] = 1. Let’s see an example.

Suppose matrix = [[0, 1], [1, 1]], it is obvious that P[0][0] = 0, P[0][1] = P[1][0] = 1, what about P[1][1]? Well, to give a square of size larger than 1 in P[1][1], all of its three neighbors (left, up, left-up) should be non-zero, right? In this case, the left-up neighbor P[0][0] = 0, so P[1][1] can only be 1, which means that it contains the square of itself.

Now you are near the solution. In fact, P[i][j] = min(P[i - 1][j], P[i][j - 1], P[i - 1][j - 1]) + 1 in this case.

Taking all these together, we have the following state equations.

  1. P[0][j] = matrix[0][j] (topmost row);
  2. P[i][0] = matrix[i][0] (leftmost column);
  3. For i > 0 and j > 0: if matrix[i][j] = 0, P[i][j] = 0; if matrix[i][j] = 1, P[i][j] = min(P[i - 1][j], P[i][j - 1], P[i - 1][j - 1]) + 1.

Putting them into codes, and maintain a variable maxsize to record the maximum size of the square we have seen, we have the following (unoptimized) solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int maximalSquare(vector<vector<char>>& matrix) {
int m = matrix.size();
if (!m) return 0;
int n = matrix[0].size();
vector<vector<int> > size(m, vector<int>(n, 0));
int maxsize = 0;
for (int j = 0; j < n; j++) {
size[0][j] = matrix[0][j] - '0';
maxsize = max(maxsize, size[0][j]);
}
for (int i = 1; i < m; i++) {
size[i][0] = matrix[i][0] - '0';
maxsize = max(maxsize, size[i][0]);
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (matrix[i][j] == '1') {
size[i][j] = min(size[i - 1][j - 1], min(size[i - 1][j], size[i][j - 1])) + 1;
maxsize = max(maxsize, size[i][j]);
}
}
}
return maxsize * maxsize;
}

Now let’s try to optimize the above solution. As can be seen, each time when we update size[i][j], we only need size[i][j - 1], size[i - 1][j - 1] (at the previous left column) and size[i - 1][j] (at the current column). So we do not need to maintain the full m*n matrix. In fact, keeping two columns is enough. Now we have the following optimized solution.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int maximalSquare(vector<vector<char>>& matrix) {
int m = matrix.size();
if (!m) return 0;
int n = matrix[0].size();
vector<int> pre(m, 0);
vector<int> cur(m, 0);
int maxsize = 0;
for (int i = 0; i < m; i++) {
pre[i] = matrix[i][0] - '0';
maxsize = max(maxsize, pre[i]);
}
for (int j = 1; j < n; j++) {
cur[0] = matrix[0][j] - '0';
maxsize = max(maxsize, cur[0]);
for (int i = 1; i < m; i++) {
if (matrix[i][j] == '1') {
cur[i] = min(cur[i - 1], min(pre[i - 1], pre[i])) + 1;
maxsize = max(maxsize, cur[i]);
}
}
swap(pre, cur);
fill(cur.begin(), cur.end(), 0);
}
return maxsize * maxsize;
}

Now you see the solution is finished? In fact, it can still be optimized! In fact, we need not maintain two vectors and one is enough. If you want to explore this idea, please refer to the answers provided by @stellari below. Moreover, in the code above, we distinguish between the 0-th row and other rows since the 0-th row has no row above it. In fact, we can make all the m rows the same by padding a 0 row on the top (in the following code, we pad a 0 on top of dp). Finally, we will have the following short code :) If you find it hard to understand, try to run it using your pen and paper and notice how it realizes what the two-vector solution does using only one vector.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int maximalSquare(vector<vector<char>>& matrix) {
if (matrix.empty()) return 0;
int m = matrix.size(), n = matrix[0].size();
vector<int> dp(m + 1, 0);
int maxsize = 0, pre = 0;
for (int j = 0; j < n; j++) {
for (int i = 1; i <= m; i++) {
int temp = dp[i];
if (matrix[i - 1][j] == '1') {
dp[i] = min(dp[i], min(dp[i - 1], pre)) + 1;
maxsize = max(maxsize, dp[i]);
}
else dp[i] = 0;
pre = temp;
}
}
return maxsize * maxsize;
}

This solution, since posted, has been suggested various improvements by kind people. For a more comprehensive collection of the solutions, please visit my technical blog.


https://discuss.leetcode.com/topic/22185/clear-c-solution-no-extra-space-12-ms

Clear C++ solution, no extra space, 12 ms.

A square with ‘1’ means any ‘0’ will interrupt counting of it’s right/down/right-down, and ‘1’ will ‘inherit’ the existing counting result.

Sine the target is a square, we shall take the smallest counting result from up/left/up-left.

So for each element ‘0’, it doesn’t inherit previous accumulated counting;

And for each element ‘1’, it takes the smallest number from left/up/left-up and add 1 to it

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int maximalSquare(vector<vector<char>>& matrix) {
int rst = 0;
for(int ii=0; ii<matrix.size(); ++ii)
{
for(int jj=0; jj<matrix[0].size(); ++jj)
{
int a = (ii&&jj) ? matrix[ii-1][jj-1] : 0;
int b = (ii) ? matrix[ii-1][jj] : 0;
int c = (jj) ? matrix[ii][jj-1] : 0;

matrix[ii][jj] = (matrix[ii][jj]>'0') ? (min(a, min(b, c))+1) : 0;

rst = max(rst, matrix[ii][jj]*matrix[ii][jj]);
}
}
return rst;
}

https://discuss.leetcode.com/topic/29332/20-lines-c-solution-using-dynamic-programming

20 lines C++ solution using dynamic programming

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {

public:

int maximalSquare(vector<vector<char>>& matrix) {
if(matrix.size()==0) return 0;
int maxSq=0;
int nRow=matrix.size();
int nCol=matrix[0].size();
vector<vector<int>> dp(nRow+1,vector<int>(nCol+1,0));
//dp[i][j] represents max square ending at position (i-1, j-1)
for(int i=1;i<=nRow;++i){
for(int j=1;j<=nCol;++j){
if(matrix[i-1][j-1]=='1'){
dp[i][j]=min(min(dp[i-1][j-1],dp[i-1][j]),dp[i][j-1])+1;
maxSq=max(maxSq,dp[i][j]);
}
}
}
return maxSq*maxSq;
}
};

https://discuss.leetcode.com/topic/15373/6-lines-visual-explanation-o-mn

6 lines, Visual Explanation, O(mn)

Explanation

What’s the largest (full-of-ones-)square ending at (i,j), meaning lower right corner in row i, column j? Imagine there are 4x4 squares above, above-left and left of it:

1
2
3
4
5
6
7
above  above-left  left

1111 1111
1111 1111 1111
1111 1111 1111
1111 1111 1111
* * 1111*

Clearly, if cell (i,j) itself is 1 as well, then there’s a 5x5 square ending at (i,j). And if there were 5x5 squares above, above-left and left of it, then we’d have a 6x6. So to find the largest square ending at (i,j), we just take the minimum size of squares ending at (i-1,j), (i-1,j-1) and (i,j-1), and add 1.

Implementation - 164 ms

I write the maximum sizes directly into the input matrix A. Cell A[i][j] will tell the side length of the largest square ending at (i,j). I go top to bottom and left to right, so (i-1,j), (i-1,j-1) and (i,j-1) have all been handled already. First thing I do for each cell is turn it into an integer, and then if it’s 1 and it’s not on the top or left border of the matrix, I determine its largest-square size as explained above. In the end, I return 0 for the empty matrix and otherwise the area of the largest square ending anywhere.

1
2
3
4
5
6
7
8
class Solution:
def maximalSquare(self, A):
for i in range(len(A)):
for j in range(len(A[i])):
A[i][j] = int(A[i][j])
if A[i][j] and i and j:
A[i][j] = min(A[i-1][j], A[i-1][j-1], A[i][j-1]) + 1
return len(A) and max(map(max, A)) ** 2

Smaller Version - 132 ms

This version is a bit smaller and faster due to using more of Python and some “tricks”:

1
2
3
4
5
6
7
8
class Solution:
def maximalSquare(self, A):
for i, r in enumerate(A):
r = A[i] = map(int, r)
for j, c in enumerate(r):
if i * j * c:
r[j] = min(A[i-1][j], r[j-1], A[i-1][j-1]) + 1
return max(map(max, A + [[0]])) ** 2

O(n) Extra Space - 128 ms

Here’s a version that doesn’t overwrite the input matrix but uses two integer lists: s tells the sizes of the squares ending it the current row and p does the same for the previous row.

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
def maximalSquare(self, A):
area = 0
if A:
p = [0] * len(A[0])
for row in A:
s = map(int, row)
for j, c in enumerate(s[1:], 1):
s[j] *= min(p[j-1], p[j], s[j-1]) + 1
area = max(area, max(s) ** 2)
p = s
return area

Note that in Python with its integer and string objects, I’m not sure this actually saves space. But in other languages, overwriting the input array might not even be possible, and if it’s possible, it might take more space than a “O(n) Extra Space” variant.


https://discuss.leetcode.com/topic/15381/my-c-code-8ms-dp-o-n-2-time-o-n-space

My C++ code, 8ms (DP, O(n^2)time, O(n) space)

The basic idea is to do DP: scan the matrix row by row (top down) and colume by colume (left to right) and for the position [i][j], the maximum square with the bottom-right corner sitting at [i][j] will have the edge length of

1
2
area[i][j]  = 0 if matrix[i][j] = '0'
= min(area[i-1][j-1], area[i][j-1], area[i-1][j]) + 1 if matrix[i][j] = '1'

For the case that matrix[i][j] = ‘1’, the algorithm tries to grow the square sitting at [i-1][j-1], area[i-1][j-1] by 1. However, it is also limitted by the bottom edge at row i and right edge at col j, which was represented by area[i][j-1] and area[i-1][j] repectively. We have to choose the min of those three values.

The DP table works on a ping-pong mode to save memory since the area recursive equation only relys on i and i-1 rows.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int maxA = 0;
const int m = matrix.size();
if(!m) return maxA;
const int n = matrix[0].size();
if(!n) return maxA;
int area[2][n]; // DP table to save the maximum square (with bottom-right corner at [i][j]) edge length
int cur = 0, next =1; // ping-pog switch index
fill_n(area[0],n,0);

int i, j;

for(i=0;i<m;i++)
{
area[next][0] = matrix[i][0] == '1'; // the first colume
for(j=1; j<n; j++)
area[next][j] = matrix[i][j]=='1'? (min(area[cur][j-1],min(area[next][j-1],area[cur][j])) + 1):0; //DP update
for(j=0; j<n && maxA<=i; j++) if(maxA<area[next][j]) maxA = area[next][j]; // find the maximum square for the current row
cur = next;
next = 1-cur;
}
return maxA * maxA;
}
};

https://discuss.leetcode.com/topic/16851/share-my-concise-python-solution

Share my concise python solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
# @param {character[][]} matrix
# @return {integer}
def maximalSquare(self, matrix):
if not matrix: return 0
m , n = len(matrix),len(matrix[0])
dp = [[0 if matrix[i][j]=='0' else 1for j in xrange(n)]for i in xrange(m)]

for i in xrange(1,m):
for j in xrange(1,n):
if matrix[i][j] =='1': dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
else: dp[i][j] = 0

ans = max([max(i) for i in dp])
return ans ** 2
谢谢你,可爱的朋友。