Maximal Square

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

                                            
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][n];
        int max = 0;
        
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(i == 0 || j == 0) {
                    dp[i][j] = matrix[i][j] - '0';
                    max = Math.max(max, dp[i][j]);
                } else if(matrix[i][j] == '1') {
                    dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j], dp[i][j-1])) + 1;
                    max = Math.max(max, dp[i][j]);
                }
            }
        }
        
        return max * max;
    }
}

                                            
class Solution(object):
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if not matrix:
            return 0
        
        rows, cols = len(matrix), len(matrix[0])
        dp = [[0] * cols for _ in range(rows)]
        max_side = 0
        
        for i in range(rows):
            for j in range(cols):
                if matrix[i][j] == "1":
                    dp[i][j] = 1
                    if i > 0 and j > 0:
                        dp[i][j] += min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
                    max_side = max(max_side, dp[i][j])
        
        return max_side * max_side

                                            
int min(int a, int b, int c) {
    int min = a;
    if (b < min) min = b;
    if (c < min) min = c;
    return min;
}

int maximalSquare(char** matrix, int matrixSize, int* matrixColSize) {
    if (matrixSize == 0 || *matrixColSize == 0) return 0;

    int maxSide = 0;
    int rows = matrixSize;
    int cols = *matrixColSize;
    int dp[rows][cols];

    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            dp[i][j] = matrix[i][j] - '0';
            if (dp[i][j] == 1) {
                maxSide = 1;
            }
        }
    }

    for (int i = 1; i < rows; i++) {
        for (int j = 1; j < cols; j++) {
            if (dp[i][j] == 1) {
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
                if (dp[i][j] > maxSide) {
                    maxSide = dp[i][j];
                }
            }
        }
    }

    return maxSide * maxSide;
}

                                            
public 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][];
        int maxLength = 0;

        for (int i = 0; i < m; i++) {
            dp[i] = new int[n];
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = matrix[i][j] - '0';
                } else if (matrix[i][j] == '1') {
                    dp[i][j] = Math.Min(dp[i - 1][j], Math.Min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                }
                maxLength = Math.Max(maxLength, dp[i][j]);
            }
        }

        return maxLength * maxLength;
    }
}

                                            
/**
 * @param {character[][]} matrix
 * @return {number}
 */
var maximalSquare = function(matrix) {
    if (matrix.length === 0) return 0;
    
    let m = matrix.length, n = matrix[0].length;
    let dp = new Array(m+1).fill(0).map(() => new Array(n+1).fill(0));
    let maxLen = 0;
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (matrix[i-1][j-1] === '1') {
                dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1;
                maxLen = Math.max(maxLen, dp[i][j]);
            }
        }
    }
    
    return maxLen * maxLen;
};

                                            
function maximalSquare(matrix: string[][]): number {
    const rows = matrix.length;
    const cols = matrix[0].length;
    let maxSide = 0;

    const dp: number[][] = Array(rows)
        .fill(0)
        .map(() => Array(cols).fill(0));

    for (let i = 0; i < rows; i++) {
        for (let j = 0; j < cols; j++) {
            if (matrix[i][j] === '1') {
                if (i === 0 || j === 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
                }
                maxSide = Math.max(maxSide, dp[i][j]);
            }
        }
    }

    return maxSide * maxSide;
};

                                            
class Solution {
    /**
     * @param String[][] $matrix
     *
     * @return Integer
     */
    function maximalSquare($matrix) {
         $max = 0;
        $rows = count($matrix);
        $cols = count($matrix[0]);
        
         $dp = array_fill(0, $rows + 1, array_fill(0, $cols + 1, 0));
        
         for($i = 1; $i <= $rows; $i++) {
            for($j = 1; $j <= $cols; $j++) {
                if($matrix[$i-1][$j-1] == '1') {
                    $dp[$i][$j] = 1 + min($dp[$i-1][$j], $dp[$i][$j-1], $dp[$i-1][$j-1]);
                    $max = max($max, $dp[$i][$j]);
                }
            }
        }
        
        return $max * $max;
    }
}

                                            
class Solution {
    func maximalSquare(_ matrix: [[Character]]) -> Int {
        var m = matrix.count
        var n = matrix[0].count
        var dp = [[Int]](repeating: [Int](repeating: 0, count: n), count: m)
        var maxSize = 0
        
        for i in 0..<m {
            for j in 0..<n {
                dp[i][j] = matrix[i][j].wholeNumberValue ?? 0
                if i > 0 && j > 0 && dp[i][j] == 1 {
                    dp[i][j] += min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))
                }
                maxSize = max(maxSize, dp[i][j])
            }
        }
        
        return maxSize * maxSize
    }
}

                                            
class Solution {
    fun maximalSquare(matrix: Array<CharArray>): Int {
        if (matrix.isEmpty()) return 0
        
        val m = matrix.size
        val n = matrix[0].size
        var maxSide = 0
        val dp = Array(m) { IntArray(n) }
        
        for (i in 0 until m) {
            for (j in 0 until n) {
                if (matrix[i][j] == '1') {
                    if (i == 0 || j == 0) {
                        dp[i][j] = 1
                    } else {
                        dp[i][j] = minOf(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
                    }
                    maxSide = maxOf(maxSide, dp[i][j])
                }
            }
        }
        
        return maxSide * maxSide
    }
}

                                            
class Solution {
  int maximalSquare(List<List<String>> matrix) {
    if (matrix.isEmpty) return 0;
    
    int m = matrix.length;
    int n = matrix[0].length;
    
    List<List<int>> dp = List.generate(m, (_) => List.filled(n, 0));
    int maxSide = 0;
    
    for (int i = 0; i < m; i++) {
      for (int j = 0; j < n; j++) {
        if (matrix[i][j] == "1") {
          if (i == 0 || j == 0) {
            dp[i][j] = 1;
          } else {
            dp[i][j] = 1 + 
              min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]));
          }
          maxSide = max(maxSide, dp[i][j]);
        }
      }
    }
    
    return maxSide * maxSide;
  }
}

                                            
func maximalSquare(matrix [][]byte) int {
    if len(matrix) == 0 || len(matrix[0]) == 0 {
        return 0
    }
    
    m := len(matrix)
    n := len(matrix[0])
    dp := make([][]int, m+1)
    for i := 0; i <= m; i++ {
        dp[i] = make([]int, n+1)
    }
    
    maxSquare := 0
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if matrix[i-1][j-1] == '1' {
                dp[i][j] = 1 + min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))
                maxSquare = max(maxSquare, dp[i][j]*dp[i][j])
            }
        }
    }
    
    return maxSquare
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

                                            
# @param {Character[][]} matrix
# @return {Integer}
def maximal_square(matrix)
    return 0 if matrix.empty? || matrix[0].empty?
    
    m = matrix.length
    n = matrix[0].length
    dp = Array.new(m) { Array.new(n, 0) }

    max_side = 0
    (0..m-1).each do |i|
        (0..n-1).each do |j|
            if matrix[i][j] == '1'
                if i == 0 || j == 0
                    dp[i][j] = 1
                else
                    dp[i][j] = [dp[i-1][j], dp[i][j-1], dp[i-1][j-1]].min + 1
                end
                max_side = [max_side, dp[i][j]].max
            end
        end
    end

    max_square = max_side * max_side
    return max_square
end

                                            
object Solution {
    def maximalSquare(matrix: Array[Array[Char]]): Int = {
        if (matrix.isEmpty) return 0
        val m = matrix.length
        val n = matrix(0).length
        val dp = Array.ofDim[Int](m, n)
        var maxLen = 0

        for (i <- 0 until m) {
            for (j <- 0 until n) {
                if (i == 0 || j == 0) {
                    dp(i)(j) = matrix(i)(j) - '0'
                } else if (matrix(i)(j) == '1') {
                    dp(i)(j) = 1 + dp(i-1)(j).min(dp(i)(j-1).min(dp(i-1)(j-1)))
                }
                maxLen = maxLen.max(dp(i)(j))
            }
        }

        maxLen * maxLen
    }
}

                                            
impl Solution {
    pub fn maximal_square(matrix: Vec<Vec<char>>) -> i32 {
        if matrix.is_empty() || matrix[0].is_empty() {
            return 0;
        }
        
        let m = matrix.len();
        let n = matrix[0].len();
        let mut dp = vec![vec![0; n+1]; m+1];
        let mut max_side = 0;
        
        for i in 1..=m {
            for j in 1..=n {
                if matrix[i-1][j-1] == '1' {
                    dp[i][j] = 1 + dp[i-1][j-1].min(dp[i-1][j].min(dp[i][j-1]));
                    max_side = max_side.max(dp[i][j]);
                }
            }
        }
        
        max_side * max_side
    }
}

To solve this coding challenge, finding the largest square containing only 1's in a binary matrix, we can utilize a dynamic programming approach. The idea is to incrementally construct the size of potential squares by leveraging already computed results. We will use a 2D list to keep track of the side length of the largest square ending at each cell in the binary matrix.

Explanation

Initial Checks and Setup :

If the matrix is empty or the dimensions are invalid, return 0 immediately.
Create dimensions
rows

and
cols

to store the number of rows and columns in the matrix, respectively.

Dynamic Programming Table Initialization :

Initialize a 2D list
dp

of the same dimensions as the matrix, filled with zeros. This will store the maximal side length of a square ending at each cell.
Initialize a variable
max_side

to track the largest side length found.

Fill the DP Table :

Traverse the matrix. For each cell
(i, j)

:

If the value is
'1'

, calculate the size of the largest square ending at that cell.
If the cell is at the top row or left column (
i == 0

or
j == 0

), the largest square ending at that cell is 1.
Otherwise, the size of the square ending at
(i, j)

is determined by the minimum of the sizes of the squares ending at the three neighboring cells [(i-1, j), (i, j-1), and (i-1, j-1)] + 1.
Update the
max_side

variable if the current cell's square is the largest found.

Calculate the Area :

The area of the largest square is
max_side * max_side

.

Pseudocode with Comments

                                            
// Function to find the maximal square area in a binary matrix
FUNCTION maximalSquare(matrix):
// Check if the input matrix is empty
IF matrix IS EMPTY:
RETURN 0

// Get the dimensions of the matrix
rows = NUMBER OF ROWS IN matrix
cols = NUMBER OF COLUMNS IN matrix

// Initialize dp table with zeros
dp = 2D LIST OF SIZE (rows x cols) WITH ALL ZEROS

// Variable to track the maximal side length of the square found
max_side = 0

// Traverse each cell in the matrix
FOR i FROM 0 TO rows-1:
FOR j FROM 0 TO cols-1:
// If the cell contains '1', calculate the side length of the largest square
IF matrix[i][j] IS '1':
// Base case: top row or left column
IF i == 0 OR j == 0:
dp[i][j] = 1
ELSE:
// Calculate the size of square ending at (i, j)
dp[i][j] = MIN(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

// Update the maximum side length found
max_side = MAX(max_side, dp[i][j])

// Return the area of the largest square
RETURN max_side * max_side

Step-by-Step Explanation of the Pseudocode

Handle empty matrix : If the matrix is empty, return 0 immediately since there's no square to form.
Dimensions setup : Store the number of rows and columns of the matrix in
rows

and
cols

.
Initialize DP Table : Create a 2D
dp

list of the same size as the matrix filled with zeros. This will store the side lengths of squares terminating at each cell.
Tracking Maximum Side Length : Create a variable
max_side

initialized to 0, which will keep the track of the largest square found.
Matrix Traversal :

For each cell
(i, j)

in the matrix, check if the cell contains
'1'

.
If it does and it is in the top row or left column, set the DP table at
(i, j)

to 1 since the only possible square is size 1.
Otherwise, calculate the largest square ending at
(i, j)

by looking at the minimum side length among the three neighbors and adding 1.
Update
max_side

to keep track of the largest square found till now.

Calculate Area : The maximal square area is computed as the square of
max_side

.

This methodology ensures efficient computation by storing intermediate results and using them to build up the final solution incrementally, achieving an optimal solution in terms of time and space complexity.