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 0Output:4

## Solution

Using dynamic programming approach.

class Solution { public int maximalSquare(char[][] matrix) { int rows = matrix.length; if(rows == 0) return 0; int cols = matrix[0].length; int[][] dp = new int[rows+1][cols+1]; int largest = 0; for(int i=1;i<=rows;i++){ for(int j=1;j<=cols;j++){ if(matrix[i-1][j-1] == '1'){ dp[i][j] = 1 + Math.min(dp[i-1][j],Math.min(dp[i][j-1],dp[i-1][j-1])); if(largest < dp[i][j]) largest = dp[i][j]; } } } return largest*largest; } }