leetcode-221 Maximal Square

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

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0

        rows, cols = len(matrix), len(matrix[0])
        # dp[i][j] = side length of max square with bottom-right at (i,j)
        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':
                    if i == 0 or j == 0:
                        # First row or column - can only be 1x1 square
                        dp[i][j] = 1
                    else:
                        # Square size = min of three neighbors + 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

    # Space optimized: O(n) space
    def maximalSquare2(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0

        rows, cols = len(matrix), len(matrix[0])
        dp = [0] * (cols + 1)
        max_side = 0
        prev = 0

        for i in range(1, rows + 1):
            for j in range(1, cols + 1):
                temp = dp[j]
                if matrix[i-1][j-1] == '1':
                    dp[j] = min(dp[j], dp[j-1], prev) + 1
                    max_side = max(max_side, dp[j])
                else:
                    dp[j] = 0
                prev = temp

        return max_side * max_side

# Time Complexity: O(m * n)
# Space Complexity: O(m * n) for 2D DP, O(n) for optimized
#
# DP Recurrence:
# If matrix[i][j] == '1':
#   dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
# Else:
#   dp[i][j] = 0
#
# Why min of three neighbors?
# - dp[i-1][j]: square above
# - dp[i][j-1]: square to the left
# - dp[i-1][j-1]: square diagonally up-left
# All three must have sufficient size to form larger square
#
# Visualization:
#   If all three neighbors have side length >= 2:
#   1 1 1     Can form 3x3 square
#   1 1 1     with (2,2) as bottom-right
#   1 1 ?
#
# AirBnB: Tests 2D DP and matrix optimization