Skip to content
Programmingoneonone
Programmingoneonone
  • Home
  • CS Subjects
    • Internet of Things (IoT)
    • Digital Communication
    • Human Values
  • Programming Tutorials
    • C Programming
    • Data structures and Algorithms
    • 100+ Java Programs
    • 100+ C Programs
  • HackerRank Solutions
    • HackerRank Algorithms Solutions
    • HackerRank C problems solutions
    • HackerRank C++ problems solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
Programmingoneonone

Leetcode Maximal Square problem solution

YASH PAL, 31 July 2024

In this Leetcode Maximal Square problem solution we have Given an m x n binary matrix filled with 0’s and 1’s, find the largest square containing only 1’s, and return its area.

Leetcode Maximal Square problem solution

Problem solution in Python.

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        
        dp=[]
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                matrix[i][j]=int(matrix[i][j])
        
           
        if len(matrix)==1 and len(matrix[0])==1:
            if matrix[0][0]==0:
                return 0
            else:
                return 1  
            
        for i in range(len(matrix)):
            x=[]
            for j in range(len(matrix[0])):
                x.append(0)
            dp.append(x) 
        side=0    
        
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j]==1:
                    side=1
                    dp[i][j]=1
        
        for i in range(1,len(matrix)):
            for j in range(1,len(matrix[0])):
                
                if matrix[i][j]==1:
                    dp[i][j]=min(dp[i-1][j-1],min(dp[i-1][j], dp[i][j-1]))+1
                    side=max(side,dp[i][j])
        
        return side*side

Problem solution in Java.

class Solution {
    public int maximalSquare(char[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m+1][n+1];
        int res = 0;
        for(int i=1; i<=m; i++) {
            for(int j=1; j<=n; j++) {
                if(matrix[i-1][j-1] == '1') {
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
                    res = Math.max(res, dp[i][j]);
                }
                
            }
        }
        
        return res * res;
    }
}

Problem solution in C++.

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

coding problems solutions

Post navigation

Previous post
Next post

Pages

  • About US
  • Contact US
  • Privacy Policy

Programing Practice

  • C Programs
  • java Programs

HackerRank Solutions

  • C
  • C++
  • Java
  • Python
  • Algorithm

Other

  • Leetcode Solutions
  • Interview Preparation

Programming Tutorials

  • DSA
  • C

CS Subjects

  • Digital Communication
  • Human Values
  • Internet Of Things
  • YouTube
  • LinkedIn
  • Facebook
  • Pinterest
  • Instagram
©2025 Programmingoneonone | WordPress Theme by SuperbThemes