HomeLeetcode221. Maximal Square - Leetcode Solutions
Leetcode

221. Maximal Square – Leetcode Solutions

Declan Clarke

Description

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.

Examples:

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

Solution in Python

Approach

  1. We create a 2D DP array (of size (m+1) x (n+1) to avoid boundary checks), where each element dp[i][j] will store the side length of the largest square whose bottom-right corner is at (i-1, j-1) in the original matrix.
  2. For each cell in the original matrix that contains a ‘1’, the corresponding value in the DP table will be the minimum of the three surrounding values (top, left, and diagonal-top-left) plus one. This works because a square can only be formed if there are ‘1’s to the left, top, and top-left of the current cell.
  3. Keep track of the maximum side length encountered, and at the end, return the area (side length squared) of the largest square.
Python
from typing import List

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        
        # Get dimensions of the matrix
        m, n = len(matrix), len(matrix[0])
        
        # Create a DP table initialized with zeros
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        # Variable to keep track of the maximum side length of a square
        max_side_length = 0
        
        # Iterate over the matrix
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                # If the current cell in the matrix contains '1'
                if matrix[i - 1][j - 1] == '1':
                    # Update the DP value: it is the min of the three neighbors + 1
                    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_length = max(max_side_length, dp[i][j])
        
        # The area of the largest square is the square of its side length
        return max_side_length ** 2

Detailed Explanation

  1. Initialization:
    We first check if the matrix is empty. If it is, we return 0 immediately. Otherwise, we initialize a DP table of size (m+1) x (n+1) filled with zeros. We also initialize a variable max_side_length to track the largest side length of a square of 1’s.
  2. Iterating over the matrix:
    We start from the first row and first column of the DP table (i = 1 and j = 1) to avoid boundary issues. For every cell in the matrix that contains ‘1’, we update the corresponding DP table entry to be the minimum of the values from the top (dp[i-1][j]), left (dp[i][j-1]), and diagonal top-left (dp[i-1][j-1]) cells, plus 1.
  3. Updating the maximum side length:
    As we update the DP table, we also check if the current side length (dp[i][j]) is the largest we have seen, and if so, update the max_side_length variable.
  4. Returning the area:
    Once we have processed the entire matrix, the area of the largest square is the square of the maximum side length, which we return.

Time and Space Complexity

  • Time complexity: O(m * n), where m is the number of rows and n is the number of columns in the matrix. We visit each cell once.
  • Space complexity: O(m * n) for the DP table, though this can be optimized to O(n) if we only keep the current and previous rows.

This solution efficiently solves the problem using dynamic programming by reducing the time complexity to linear with respect to the number of cells in the matrix.

Solution in Javascript

JavaScript
var maximalSquare = function(matrix) {
    // If matrix is empty, return 0
    if (matrix.length === 0 || matrix[0].length === 0) return 0;
    
    // Get the dimensions of the matrix
    let m = matrix.length;
    let n = matrix[0].length;
    
    // Create a DP array initialized to 0 with dimensions (m+1) x (n+1)
    let dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));
    
    // Variable to track the maximum side length of a square
    let maxSideLength = 0;
    
    // Loop through the matrix, starting from index (1, 1) in the dp array
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            // If the current cell in the matrix contains '1'
            if (matrix[i - 1][j - 1] === '1') {
                // Update dp[i][j] based on the minimum of the three neighbors plus 1
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
                
                // Update the maximum side length found so far
                maxSideLength = Math.max(maxSideLength, dp[i][j]);
            }
        }
    }
    
    // The area of the largest square is the square of its side length
    return maxSideLength * maxSideLength;
};

Solution in Java

Java
class Solution {
    public int maximalSquare(char[][] matrix) {
        // If matrix is empty, return 0
        if (matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        // Get the dimensions of the matrix
        int m = matrix.length;
        int n = matrix[0].length;

        // Create a DP table initialized with 0, of size (m+1) x (n+1)
        int[][] dp = new int[m + 1][n + 1];

        // Variable to track the maximum side length of a square
        int maxSideLength = 0;

        // Iterate through the matrix
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // If the current cell in the matrix contains '1'
                if (matrix[i - 1][j - 1] == '1') {
                    // Update dp[i][j] based on the minimum of the three neighbors plus 1
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;

                    // Update the maximum side length found so far
                    maxSideLength = Math.max(maxSideLength, dp[i][j]);
                }
            }
        }

        // The area of the largest square is the square of its side length
        return maxSideLength * maxSideLength;
    }
}

Solution in C#

C#
public class Solution {
    public int MaximalSquare(char[][] matrix) {
        // If the matrix is empty, return 0
        if (matrix.Length == 0 || matrix[0].Length == 0) {
            return 0;
        }

        // Get the number of rows (m) and columns (n) of the matrix
        int m = matrix.Length;
        int n = matrix[0].Length;

        // Create a DP array with dimensions (m+1) x (n+1) initialized to 0
        int[,] dp = new int[m + 1, n + 1];

        // Variable to track the maximum side length of a square
        int maxSideLength = 0;

        // Iterate over the matrix starting from (1, 1) in the DP table
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // If the current cell in the matrix contains '1'
                if (matrix[i - 1][j - 1] == '1') {
                    // Update dp[i, j] based on the minimum of the three neighbors (top, left, diagonal-top-left) plus 1
                    dp[i, j] = Math.Min(dp[i - 1, j], Math.Min(dp[i, j - 1], dp[i - 1, j - 1])) + 1;
                    
                    // Update the maximum side length found so far
                    maxSideLength = Math.Max(maxSideLength, dp[i, j]);
                }
            }
        }

        // The area of the largest square is the square of its side length
        return maxSideLength * maxSideLength;
    }
}

Related Post

Subscribe
Notify of

0 Comments
Inline Feedbacks
View all comments

Popular

© 2024 Devexplain.com