Maximal Square

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.

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.

test

Solution

Explanation will be added.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int rowSize = matrix.size(), colSize = rowSize? matrix[0].size():0;
vector<vector<int>> square(rowSize+1, vector<int>(colSize+1, 0));
int maxWidth = 0;
for(int r = 1; r <= rowSize; ++r) {
for(int c = 1; c <= colSize; ++c) {
if(matrix[r-1][c-1] == '1')
square[r][c] = min(min(square[r-1][c], square[r][c-1]), square[r-1][c-1]) + 1;
maxWidth = max(maxWidth, square[r][c]);
}
}
return maxWidth*maxWidth;
}
};

Always welcome new ideas and practical tricks, just leave them in the comments!