Maximal Square

1. Problem Description

In a 2D matrix consisting of '0' and '1', find the largest square containing only '1' and return its area.

2. Approach

1. Approach 1
   • Similar to Number of Islands: when a 1 is encountered, treat it as the top-left corner and see how large the side length can grow

3. Implementation

3.1. Brute Force

package main

func maximalSquare(matrix [][]byte) int {
	rows := len(matrix)
	cols := len(matrix[0])

	maxSide := 0
	for row := 0; row < rows; row++ {
		for col := 0; col < cols; col++ {
			side := Min(rows-row, cols-col)
			if matrix[row][col] == '1' && side > maxSide {
				maxSide = Max(maxSide, maxSquare(matrix, row, col, side))
			}
		}
	}

	return maxSide * maxSide
}

// Use data[row][col] as the top-left corner and check for a square with side length side
func maxSquare(data [][]byte, row, col, side int) int {
	max := 0
	for currentSide := 0; currentSide < side; currentSide++ {
		for i := 0; i <= currentSide; i++ {
			if data[row+currentSide][col+i] == '0' {
				return max
			}
			if data[row+i][col+currentSide] == '0' {
				return max
			}
		}
		max += 1
	}

	return max
}

func Min(a int, b int) int {
	if a < b {
		return a
	}
	return b
}

func Max(data ...int) int {
	max := data[0]
	for i := 1; i < len(data); i++ {
		if data[i] > max {
			max = data[i]
		}
	}
	return max
}

4. References

• 221. Maximal Square - LeetCode