221.maximal-square.md

221. Maximal Square

Brute Force

fun maximalSquare(matrix: Array<CharArray>): Int {
    val m = matrix.size
    val n = matrix[0].size

    var maxSquare = 0
    for (row in 0 until m) {
        for (col in 0 until n) {
            var i = row
            var j = col
            var currentLength = if (matrix[i][j] == '1') 1 else 0
            if (currentLength == 0) continue
            while (i + 1 < m && j + 1 < n && matrix[i + 1][j + 1] == '1') {
                var allOnes = true
                for (r in row..i) {
                    if (matrix[r][j + 1] == '0') {
                        allOnes = false
                        break
                    }
                }
                if (!allOnes) break
                for (c in col..j) {
                    if (matrix[i + 1][c] == '0') {
                        allOnes = false
                        break
                    }
                }

                if (allOnes) {
                    currentLength++
                } else {
                    break
                }
                i++
                j++
            }

            maxSquare = max(maxSquare, currentLength * currentLength)
        }
    }
    return maxSquare
}

Dynamic Programming

fun maximalSquare(matrix: Array<CharArray>): Int {
    val dp = Array(matrix.size) { _ -> IntArray(matrix[0].size) }
    var longestLength = 0
    for (i in 0 until matrix.size) {
        for (j in 0 until matrix[0].size) {
            dp[i][j] = if (matrix[i][j] == '0') 0 else {
                if (i == 0 || j == 0) 1
                else min(
                    dp[i - 1][j - 1],
                    min(dp[i - 1][j], dp[i][j - 1])
                ) + 1
            }
            longestLength = max(longestLength, dp[i][j])
        }
    }
    return longestLength * longestLength
}