Maximal Square

LeetCode Q 221 - 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.

Example:
Input:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Output: 4

Solution :

1. State: dp(i,j) represents the side length of the maximum square whose bottom right corner is the cell with index (i,j) in the original matrix.

2. state transfer fuction:
   Starting from index (0,0), for every 1 found in the original matrix, we update the value of the current element as
   dp(i, j)=min(dp(i−1, j), dp(i−1, j−1), dp(i, j−1)) + 1.

Time Complexity: O(n * m)
Space Complexity: O(n * m)

Code:

public int maximalSquare(char[][] matrix) {
	if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
		return 0;

	int row = matrix.length, col = matrix[0].length;
	int[][] dp = new int[row + 1][col + 1];
	
	int maxLen = 0;
	for (int i = 0; i < matrix.length; i++) {
		for (int j = 0; j < matrix[0].length; j++) {
			if (matrix[i][j] == '1') {
				dp[i+1][j+1] = Math.min(Math.min(dp[i][j], dp[i+1][j]), dp[i][j+1]) + 1;
				maxLen = Math.max(maxLen, dp[i+1][j+1]);
			}
		}
	}
	
	return maxLen * maxLen;
}