Maximal Square

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> dp(n + 1, 0);
        int best = 0, prev = 0;
        for (int r = 0; r < m; ++r) {
            for (int c = 1; c <= n; ++c) {
                int temp = dp[c];
                if (matrix[r][c - 1] == '1') {
                    dp[c] = 1 + min({dp[c], dp[c - 1], prev});
                    best = max(best, dp[c]);
                } else {
                    dp[c] = 0;
                }
                prev = temp;
            }
        }
        return best * best;
    }
};

func maximalSquare(matrix [][]byte) int {
    m, n := len(matrix), len(matrix[0])
    dp := make([]int, n+1)
    best, prev := 0, 0
    for r := 0; r < m; r++ {
        prev = 0
        for c := 1; c <= n; c++ {
            temp := dp[c]
            if matrix[r][c-1] == '1' {
                a, b := dp[c], dp[c-1]
                if b < a {
                    a = b
                }
                if prev < a {
                    a = prev
                }
                dp[c] = 1 + a
                if dp[c] > best {
                    best = dp[c]
                }
            } else {
                dp[c] = 0
            }
            prev = temp
        }
    }
    return best * best
}

from typing import List

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [0] * (n + 1)
        best = 0
        for r in range(m):
            prev = 0
            for c in range(1, n + 1):
                temp = dp[c]
                if matrix[r][c - 1] == '1':
                    dp[c] = 1 + min(dp[c], dp[c - 1], prev)
                    if dp[c] > best:
                        best = dp[c]
                else:
                    dp[c] = 0
                prev = temp
        return best * best

function maximalSquare(matrix) {
    const m = matrix.length, n = matrix[0].length;
    const dp = new Array(n + 1).fill(0);
    let best = 0;
    for (let r = 0; r < m; r++) {
        let prev = 0;
        for (let c = 1; c <= n; c++) {
            const temp = dp[c];
            if (matrix[r][c - 1] === '1') {
                dp[c] = 1 + Math.min(dp[c], dp[c - 1], prev);
                if (dp[c] > best) best = dp[c];
            } else {
                dp[c] = 0;
            }
            prev = temp;
        }
    }
    return best * best;
}

class Solution {
    public int maximalSquare(char[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[] dp = new int[n + 1];
        int best = 0;
        for (int r = 0; r < m; r++) {
            int prev = 0;
            for (int c = 1; c <= n; c++) {
                int temp = dp[c];
                if (matrix[r][c - 1] == '1') {
                    dp[c] = 1 + Math.min(Math.min(dp[c], dp[c - 1]), prev);
                    if (dp[c] > best) best = dp[c];
                } else {
                    dp[c] = 0;
                }
                prev = temp;
            }
        }
        return best * best;
    }
}

function maximalSquare(matrix: string[][]): number {
    const m = matrix.length, n = matrix[0].length;
    const dp: number[] = new Array(n + 1).fill(0);
    let best = 0;
    for (let r = 0; r < m; r++) {
        let prev = 0;
        for (let c = 1; c <= n; c++) {
            const temp = dp[c];
            if (matrix[r][c - 1] === '1') {
                dp[c] = 1 + Math.min(dp[c], dp[c - 1], prev);
                if (dp[c] > best) best = dp[c];
            } else {
                dp[c] = 0;
            }
            prev = temp;
        }
    }
    return best * best;
}