Maximal Square – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

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.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Example 3:

Input: matrix = [["0"]]
Output: 0

Constraints:

• m == matrix.length
• n == matrix[i].length
• 1 <= m, n <= 300
• matrix[i][j] is '0' or '1'.

C++ Maximal Square LeetCode Solution

class Solution {
public:
    int maximalSquare(vector<vector<char>>& M) {
        auto isValidSquare = [&](int i, int j, int side) {
            return all_of(begin(M)+i, begin(M)+i+side, [&](auto& R){
                return all_of(begin(R)+j, begin(R)+j+side, [&](auto cell) { return cell == '1'; });
            });
        };
        int m = size(M), n = size(M[0]);
        for(int sideLen = min(m, n); sideLen; sideLen--)
            for(int row = 0; row <= m-sideLen; row++)
                for(int col = 0; col <= n-sideLen; col++)
                    if(isValidSquare(row, col, sideLen))
                        return sideLen*sideLen;
        return 0;
    }
};

Java Maximal Square LeetCode Solution

public int maximalSquare(char[][] a) {
    if(a.length == 0) return 0;
    int m = a.length, n = a[0].length, result = 0;
    int[][] b = new int[m+1][n+1];
    for (int i = 1 ; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if(a[i-1][j-1] == '1') {
                b[i][j] = Math.min(Math.min(b[i][j-1] , b[i-1][j-1]), b[i-1][j]) + 1;
                result = Math.max(b[i][j], result); // update result
            }
        }
    }
    return result*result;
}
 

Python 3 Maximal Square LeetCode Solution

class Solution:
    def maximalSquare(self, M):
        def is_valid_sqaure(row, col, side):
            return all(all(M[i][j] == '1' for j in range(col, col+side)) for i in range(row, row+side))
        m, n = len(M), len(M[0])
        for side_len in range(min(m,n), 0, -1):
            for row in range(m - side_len + 1):
                for col in range(n - side_len + 1):
                    if is_valid_sqaure(row, col, side_len):
                        return side_len**2
        return 0

Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1

Leave a comment below

Related posts:

Maximal Rectangle – LeetCode Solution Next Permutation – LeetCode Solution Insert Interval – LeetCode Solution Remove Duplicates from Sorted Array II – LeetCode Solution Gas Station – LeetCode Solution House Robber II – LeetCode Solution