Maximal Square

Given a 2D binary matrix, find the largest square containing only 1s and return its area. A brute-force check of all squares is too slow.

Function signature

func MaximalSquare(matrix [][]byte) int

Inputs / outputs

• matrix: grid of '0' and '1'.
• Return: area of the largest all-1s square.

Example

10100
10111
11111
10010
Largest square has side 2 -> area 4

Constraints

• 1 <= m, n <= 300

Core idea (near-solution)

DP where dp[r][c] is the side length of the largest square ending at (r,c). It depends on top, left, and top-left.

Invariant: dp values for previous row/column are already computed when processing (r,c).

Algorithm (step-by-step)

1. Initialize dp with an extra leading 0 column to simplify boundaries.
2. For each cell (r,c):
   • If matrix[r][c] == '1', set dp[c] = 1 + min(dp[c], dp[c-1], prev).
   • Else dp[c] = 0.
   • Track max side length.
3. Return maxSide^2.

Correctness sketch

• Invariant: dp values for previous row/column are already computed when processing (r,c).
• The DP state represents the optimal answer for a prefix or subproblem.
• The recurrence uses only previously solved states, preserving correctness.
• The final DP value (or max over DP) is the correct answer.

Trace (hand walkthrough)

Example input:
10100
10111
11111
10010
Largest square has side 2 -> area 4

Walk:
- dp computes max side 2 around rows 1-2, cols 2-3
- max side=2 -> area=4

Pitfalls to avoid

• Confusing area with side length.
• Not resetting dp[c] to 0 when matrix cell is '0'.

Complexity

• Time: O(m*n).
• Extra space: O(n).

Implementation notes (Go)

• Use a rolling dp slice and a prev variable for top-left.