Maximal Square

def maximalSquare(matrix):
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    best = 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] = 1 + min(dp[i - 1][j],      # up
                                   dp[i][j - 1],      # left
                                   dp[i - 1][j - 1])  # diagonal
                best = max(best, dp[i][j])
    return best * best

Maximal Square. Picture a solar farm: ones are working panels, zeros are broken. Find the largest square made only of working panels, and return its area.

In this four by five field, the biggest is two by two: area four. In zero one, one zero, it's a single panel: one. All zeros give zero.

The naive way starts at every cell and grows a square while it stays all ones, rechecking every cell inside. That's roughly m times n, squared.

Instead, give each panel one number: the side of the largest square whose bottom-right corner is that panel. A broken panel gets zero. A working one looks up, left, and diagonally up-left. A square of side k plus one needs a side k square at all three, so the smallest one is the limit: one plus their minimum.

In code, pad the table with zeros. For every one, store one plus the minimum of top, left and diagonal, and track the largest side. Return it squared.

Back to the field. The top row and left column copy the panels. In row two, each one touches a zero, so it stays one. In row three, column four sees one, one, one: it becomes two. Its neighbour sees one, two, one: the minimum caps it at two. The largest side is two, so the area is four.

Each cell is constant work: order m times n time, and m times n space, or just one row, order n.

Look up, left and diagonal, take the smallest, add one. That's Maximal Square.