Solution For Maximal Square

The Maximal Square problem on LeetCode is a dynamic programming problem that asks you to find the area of the largest square formed in a 2D binary matrix (a matrix consisting of only 0’s and 1’s).

To solve this problem, we will use dynamic programming. We will create a 2D array where each element (i, j) represents the size of the largest square that can be formed using the bottom right corner of the (i, j) element. We will fill this array by iterating over the matrix and calculating the size of the largest square each (i, j) element can form by considering the (i-1, j), (i-1, j-1), and (i, j-1) elements.

Let’s look at the steps in detail:

Step 1: Initialize a 2D array with the same size as the input matrix, and fill the first row and first column with the corresponding values of the input matrix.

Step 2: Traverse through the remaining elements of the array. If the current element in the input matrix is 1, then calculate the maximum size of the square that can be formed using the current element as the bottom right corner, and update the 2D array.

To calculate the maximum size of the square, we check the values of its three adjacent elements in the 2D array (top, diagonal, left). The largest square that can be formed in this position will be 1 + the minimum size of the square that can be formed using these three elements.

At each iteration, we keep track of the maximum size of the squares calculated so far.

Step 3: Return the area of the largest square calculated.

Here is a sample implementation in Python:

“`
def maximalSquare(matrix):
“””
:type matrix: List[List[str]] :rtype: int
“””
if not matrix:
return 0

m, n = len(matrix), len(matrix[0])
dp_table = [[0]*n for _ in range(m)]
max_area = 0

# fill first row and col
for i in range(m):
    dp_table[i][0] = int(matrix[i][0])
    max_area = max(max_area, dp_table[i][0])
for j in range(n):
    dp_table[0][j] = int(matrix[0][j])
    max_area = max(max_area, dp_table[0][j])

# fill rest of the matrix
for i in range(1, m):
    for j in range(1, n):
        if matrix[i][j] == '1':
            dp_table[i][j] = 1 + min(dp_table[i-1][j], dp_table[i][j-1], dp_table[i-1][j-1])
            max_area = max(max_area, dp_table[i][j]**2)

return max_area

“`

Time Complexity: O(mn)
Space Complexity: O(mn)

Step by Step Implementation For Maximal Square

class Solution {
    public int maximalSquare(char[][] matrix) {
        // check for empty matrix
        if (matrix == null || matrix.length == 0) {
            return 0;
        }
 
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] dp = new int[rows + 1][cols + 1];
        int maxsqlen = 0;
 
        // dp[i][j] represents the side length of the maximum square 
        // whose bottom right corner is at (i, j)
 
        // fill the dp table
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                if (matrix[i-1][j-1] == '1') {
                    dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), 
                                        dp[i - 1][j - 1]) + 1;
                    maxsqlen = Math.max(maxsqlen, dp[i][j]);
                }
            }
        }
 
        return maxsqlen * maxsqlen;
    }
}

def maximalSquare(matrix):
        # Base case
        if not matrix:
            return 0
        
        # Store the number of rows and columns in the matrix
        rows = len(matrix)
        cols = len(matrix[0])
        
        # Create a 2D array to store the length of the largest square 
        # with each cell as the bottom-right corner
        dp = [[0] * cols for _ in range(rows)]
        
        # Initialize the max side length to 0
        max_side = 0
        
        # Iterate over the matrix
        for i in range(rows):
            for j in range(cols):
                
                # If the current cell is 0, then it cannot be part of a square
                if matrix[i][j] == '0':
                    continue
                
                # If we are at the top or left edge of the matrix, 
                # the largest square that can be formed with this cell 
                # as the bottom-right corner is just 1
                if i == 0 or j == 0:
                    dp[i][j] = 1
                
                # Otherwise, the largest square that can be formed with 
                # this cell as the bottom-right corner is the minimum 
                # of the lengths of the squares with the cell to the 
                # left, top, and top-left as the bottom-right corner, 
                # plus 1
                else:
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                
                # Update the max side length
                max_side = max(max_side, dp[i][j])
        
        # The max square will have side length max_side^2
        return max_side ** 2

/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function(matrix) {
    // check for empty matrix
    if (matrix.length == 0) {
        return 0;
    }
    
    // initialize dp matrix and fill first row and column
    let dp = new Array(matrix.length+1);
    for (let i = 0; i <= matrix.length; i++) {
        dp[i] = new Array(matrix[0].length+1);
        dp[i].fill(0);
    }
    
    // fill dp matrix
    let max = 0;
    for (let i = 1; i <= matrix.length; i++) {
        for (let j = 1; j <= matrix[0].length; j++) {
            if (matrix[i-1][j-1] == '1') {
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
                max = Math.max(max, dp[i][j]);
            }
        }
    }
    
    // return max value
    return max * max;
};

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

using System; 

public class Solution { 

public int MaximalSquare(char[][] matrix) { 

// check for empty matrix 
if (matrix == null || matrix.Length == 0) { 
return 0; 
} 

// dp[i, j] represents the length of the side of the 
// largest square that can be achieved using the 
// ith row and the jth column as the bottom right 
// corner of the square 
int[,] dp = new int[matrix.Length, matrix[0].Length]; 

// initialize the dp matrix 
for (int i = 0; i < matrix.Length; i++) { 
for (int j = 0; j < matrix[0].Length; j++) { 
dp[i, j] = matrix[i][j] - '0'; 
} 
} 

// fill in the dp matrix 
for (int i = 1; i < matrix.Length; i++) { 
for (int j = 1; j < matrix[0].Length; j++) { 

// if the current cell is '1', update the value 
// of the cell to the length of the side of the 
// largest square that can be achieved using the 
// current cell as the bottom right corner of the 
// square 
if (matrix[i][j] == '1') { 
dp[i, j] = Math.Min(Math.Min(dp[i - 1, j], dp[i, j - 1]), dp[i - 1, j - 1]) + 1; 
} 
} 
} 

// return the maximum value in the dp matrix 
int max = 0; 

for (int i = 0; i < matrix.Length; i++) { 
for (int j = 0; j < matrix[0].Length; j++) { 
max = Math.Max(max, dp[i, j]); 
} 
} 

return max * max; 
} 
}