Maximal Square

Hi Geeks! In this article, we going to see about Maximal Square Problem.

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

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;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s