Maximal Square medium

Problem Statement

Given an m x n binary matrix 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

Steps

The problem can be efficiently solved using dynamic programming. We'll create a DP table of the same dimensions as the input matrix. Each cell dp[i][j] will store the size of the largest square ending at matrix[i][j].

1. Initialization: The first row and column of the DP table are initialized directly from the input matrix. If matrix[i][j] == '0', dp[i][j] = 0; otherwise, dp[i][j] = 1.

2. Iteration: We iterate through the remaining cells of the DP table. For each cell dp[i][j], we check if matrix[i][j] == '1'. If it is, the size of the square ending at this cell is determined by the minimum of the three adjacent cells: dp[i-1][j], dp[i][j-1], and dp[i-1][j-1], plus 1. This is because a larger square can only be formed if the cells above, to the left, and diagonally above and to the left all contain 1s.

3. Finding the Maximum: After filling the DP table, we iterate through it to find the maximum value, which represents the side length of the largest square. The area is then the square of this side length.

Explanation

The dynamic programming approach optimizes the solution by avoiding redundant calculations. Instead of checking all possible squares, it builds up the solution incrementally. Each cell's value depends only on the values of its neighboring cells, making the computation efficient. The minimum of the three adjacent cells ensures that we only consider squares that are actually composed entirely of 1s.

Code

function maximalSquare(matrix: string[][]): number {
    const rows = matrix.length;
    const cols = matrix[0].length;
    const dp: number[][] = Array(rows).fill(0).map(() => Array(cols).fill(0));
    let maxSize = 0;

    // Initialize first row and column
    for (let i = 0; i < rows; i++) {
        if (matrix[i][0] === '1') {
            dp[i][0] = 1;
            maxSize = 1;
        }
    }
    for (let j = 0; j < cols; j++) {
        if (matrix[0][j] === '1') {
            dp[0][j] = 1;
            maxSize = 1;
        }
    }

    // Iterate and fill the DP table
    for (let i = 1; i < rows; i++) {
        for (let j = 1; j < cols; j++) {
            if (matrix[i][j] === '1') {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1;
                maxSize = Math.max(maxSize, dp[i][j]);
            }
        }
    }

    return maxSize * maxSize;
};

Complexity

• Time Complexity: O(m*n), where 'm' and 'n' are the dimensions of the matrix. We iterate through the matrix once to build the DP table and once to find the maximum value.
• Space Complexity: O(m*n), as we use a DP table of the same size as the input matrix. This could be optimized to O(min(m,n)) by using only a 1D array.