Solutions

1. Brute Force

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        res = 0

        for r in range(m):
            for c in range(n):
                if matrix[r][c] == "0":
                    continue
                k = 1
                while True:
                    if r + k > m or c + k > n:
                        break
                    flag = True

                    for i in range(r, r + k):
                        if matrix[i][c + k - 1] == "0":
                            flag = False
                            break
                    for j in range(c, c + k):
                        if matrix[r + k - 1][j] == "0":
                            flag = False
                            break

                    if not flag:
                        break
                    res = max(res, k * k)
                    k += 1

        return res

Time & Space Complexity

Time complexity: $O((m * n) ^ 2)$
Space complexity: $O(1)$

Where $m$ is the number of rows and $n$ is the number columns.

2. Dynamic Programming (Top-Down)

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        ROWS, COLS = len(matrix), len(matrix[0])
        cache = {}

        def dfs(r, c):
            if r >= ROWS or c >= COLS:
                return 0
            if (r, c) not in cache:
                down = dfs(r + 1, c)
                right = dfs(r, c + 1)
                diag = dfs(r + 1, c + 1)
                cache[(r, c)] = 0
                if matrix[r][c] == "1":
                    cache[(r, c)] = 1 + min(down, right, diag)
            return cache[(r, c)]

        dfs(0, 0)
        return max(cache.values()) ** 2

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ is the number of rows and $n$ is the number columns.

3. Dynamic Programming (Bottom-Up)

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        max_square = 0

        for r in range(m - 1, -1, -1):
            for c in range(n - 1, -1, -1):
                if matrix[r][c] == "1":
                    dp[r][c] = 1 + min(dp[r + 1][c], dp[r][c + 1], dp[r + 1][c + 1])
                    max_square = max(max_square, dp[r][c])

        return max_square * max_square

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ is the number of rows and $n$ is the number columns.

4. Dynamic Programming (Space Optimized)

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [0] * (n + 1)
        max_square = 0

        for r in range(m - 1, -1, -1):
            prev = 0
            for c in range(n - 1, -1, -1):
                temp = dp[c]
                if matrix[r][c] == "1":
                    dp[c] = 1 + min(dp[c], dp[c + 1], prev)
                    max_square = max(max_square, dp[c])
                else:
                    dp[c] = 0
                prev = temp

        return max_square * max_square

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(n)$

Where $m$ is the number of rows and $n$ is the number columns.