Maximal Square

MEDIUM

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.

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'.

Approaches

Checkout 3 different approaches to solve Maximal Square. Click on different approaches to view the approach and algorithm in detail.

Brute Force Approach

Check every possible square in the matrix by iterating through each cell as a potential top-left corner of a square and expanding the size until we find the largest valid square.

Algorithm

Iterate through each cell in the matrix
If a cell contains '1', try to expand it into a square
For each expansion:
- Check if all cells in the new row and column are '1's
- If yes, continue expanding
- If no, stop and update maximum square length if necessary
Return the area of the largest square found

For each cell in the matrix that contains '1', we try to expand it into a square by checking if all cells within the potential square are '1's. We keep track of the maximum square size found.

class Solution {
    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0) return 0;
        
        int rows = matrix.length;
        int cols = matrix[0].length;
        int maxSquareLen = 0;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    int squareLen = 1;
                    boolean flag = true;
                    
                    // Try to expand the square while staying within bounds
                    while (i + squareLen < rows && j + squareLen < cols && flag) {
                        // Check the new row and column to be added
                        for (int k = j; k <= j + squareLen; k++) {
                            if (matrix[i + squareLen][k] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        
                        for (int k = i; k <= i + squareLen; k++) {
                            if (matrix[k][j + squareLen] == '0') {
                                flag = false;
                                break;
                            }
                        }
                        
                        if (flag) squareLen++;
                    }
                    
                    maxSquareLen = Math.max(maxSquareLen, squareLen);
                }
            }
        }
        
        return maxSquareLen * maxSquareLen;
    }
}

Complexity Analysis

Time Complexity: O(m*n*min(m,n)^2) where m and n are the dimensions of the matrix. For each cell, we might need to check up to min(m,n) cells in both directions.Space Complexity: O(1) as we only use a constant amount of extra space

Pros and Cons

Pros:

Simple to understand and implement
No extra space required except for a few variables

Cons:

Very inefficient for large matrices
Performs redundant checks on the same cells multiple times
Time complexity is cubic in the worst case

Code Solutions

Checking out 4 solutions in different languages for Maximal Square. Click on different languages to view the code.

public class Solution {
    public int MaximalSquare(char[][] matrix) {
        int m = matrix.Length, n = matrix[0].Length;
        var dp = new int[m + 1, n + 1];
        int mx = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (matrix[i][j] == '1') {
                    dp[i + 1, j + 1] = Math.Min(Math.Min(dp[i, j + 1], dp[i + 1, j]), dp[i, j]) + 1;
                    mx = Math.Max(mx, dp[i + 1, j + 1]);
                }
            }
        }
        return mx * mx;
    }
}

Video Solution

Watch the video walkthrough for Maximal Square

Patterns:

Dynamic Programming

Data Structures:

ArrayMatrix

Companies:

Airbnb |ByteDance |Goldman Sachs |Karat |