LeetCode Q221: Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 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.

Solution:
DP, at each entry, need to check its left, up and upleft entries. Add one to the smallest entry of the three. If current entry is 0, then keep as it is.

	class Solution {
	public:
	int maximalSquare(vector<vector<char>>& matrix) {
	int largest=0;
	if(matrix.empty())
	return largest;
	for(int i=0; i<matrix.size(); i++){
	for(int j=0; j<matrix[0].size(); j++){
	int a = i==0||j==0? 0: matrix[i-1][j-1]-'0';
	int b = i==0? 0:matrix[i-1][j]-'0';
	int c = j==0? 0:matrix[i][j-1]-'0';
	matrix[i][j] = matrix[i][j]=='0'? '0':(min(a, min(b, c))+1)+'0';
	largest = max(largest, int(matrix[i][j]-'0'));
	}
	}
	return largest*largest;
	}
	};

view raw Q221MaximalSquare.cpp hosted with ❤ by GitHub

Round 2 solution:

	class Solution {
	public:
	int maximalSquare(vector<vector<char>>& matrix) {
	if(matrix.empty())
	return 0;
	vector<vector<int> > myT(matrix.size()+1, vector<int>(matrix[0].size()+1, 0));
	for(int i=1; i<myT.size(); i++)
	for(int j=1; j<myT[0].size(); j++)
	myT[i][j]=matrix[i-1][j-1]-'0';
	int maxArea=0;
	for(int i=1; i<myT.size(); i++)
	for(int j=1; j<myT[0].size(); j++){
	if(matrix[i-1][j-1]!='1')
	continue;
	myT[i][j] = min(myT[i][j-1], min(myT[i-1][j], myT[i-1][j-1]))+1;
	maxArea = max(maxArea, myT[i][j]*myT[i][j]);
	}
	return maxArea;
	}
	};

view raw Q221Rnd2.cpp hosted with ❤ by GitHub