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 dp of the same dimensions as the input matrix. dp[i][j] will store the side length of the largest square ending at matrix[i][j].

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

2. Iteration: We iterate through the remaining cells of matrix. For each cell matrix[i][j], if it's '1', we look at the cells diagonally above and to the left (dp[i-1][j-1]), directly above (dp[i-1][j]), and directly to the left (dp[i][j-1]).

3. DP Calculation: dp[i][j] will be the minimum of these three values plus 1. This is because the largest square ending at matrix[i][j] can only be one unit larger than the smallest of the squares ending at its adjacent cells.

4. Finding the Maximum: As we iterate, we track the maximum value in dp. This maximum value represents the side length of the largest square. The area is then the square of this maximum side length.

Explanation

The dynamic programming approach cleverly leverages the fact that to build a larger square, we need smaller squares around it. By building up the dp table from top-left to bottom-right, we are efficiently reusing previously computed results, avoiding redundant calculations. This makes the algorithm much faster than a brute-force approach.

Code

def maximalSquare(matrix):
    """
    Finds the largest square containing only 1's in a binary matrix.

    Args:
        matrix: A list of lists representing the binary matrix.

    Returns:
        The area of the largest square.
    """
    m = len(matrix)
    if m == 0:
        return 0
    n = len(matrix[0])
    dp = [[0] * (n + 1) for _ in range(m + 1)]  #Adding extra row and column for easy boundary handling
    max_side = 0

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if matrix[i - 1][j - 1] == '1':
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                max_side = max(max_side, dp[i][j])

    return max_side * max_side

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.
• Space Complexity: O(m*n), due to the space used by the DP table dp. We can optimize this to O(min(m,n)) by using only a single row or column of the DP table if needed.