leetcode-go/medium/221.maximal-square.go

func maximalSquare(matrix [][]byte) int {
	n := len(matrix)
	if n == 0 {
		return 0
	}
	m := len(matrix[0])
	if m == 0 {
		return 0
	}
	sideLen, sideMax := m, 0
	if n < m {
		sideLen = n
	}
	hei := make([][]int, n) // Init the accumulative height matrix
	hei[0] = make([]int, m)
	combo := make([]int, sideLen+1)
	for i := range matrix[0] {
		hei[0][i] = int(matrix[0][i]-'0')
		if hei[0][i] == 1 {
			sideMax = 1
		}
	}
	for i := 1; i < n; i++ {
		hei[i] = make([]int, m)
		combo = make([]int, sideLen+1)
		for j := range matrix[i] {
			if matrix[i][j] == '0' {
				hei[i][j] = 0
				for k := sideMax+1; k <= sideLen; k++ {
					combo[k] = 0
				}
			} else {
				hei[i][j] = hei[i-1][j] + 1
				for k := sideMax+1; k <= sideLen && k <= hei[i][j]; k++ {
					combo[k]++
					if combo[k] == k {
						sideMax = k
					}
				}
				for k := hei[i][j]+1; k <= sideLen; k++ {
					combo[k] = 0
				}
			}
		}
	}
	return sideMax * sideMax
}