We try to iterate every possible, then pick a 1 and try to expand it downwards and rightwards to see how big the square gets.
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
}The problem of brute force is that it's computationally expensive, we have to check every single '1' as a potential top-left corner of the square, then expand it downwards and rightwards to check every possible size.
Instead of looking forward (trying to expand), we look **backward by checking previous calculations), this is the key to dynamic programming.
For each single '1', we check "If am the bottom-right corners, how big the square can be?" To answer this question, we don't need to expand or look at the whole matrix, we only need to check its 3 neighbors: the top-left corner, the top edge, and the left edge.
(i-1, j-1) (i-1, j)
\ |
(i, j-1) - (i, j)Q: Why do we check the 3 neighbors only? Image we are building a wooden table, and we are currently holding a
1 x 1square (the current cell), and we want to attach to the existing structure to form a larger square. (Fill in the right-bottom corner)
Q: Why do we need to check "top-left" corner as well? Checking
topandlefttells the edges, but checking "top-left" corner tells the corner (or center) is filled. Let's take an example, we check the bottom-right cell?:
0, 1
1, ?If we only check top and left, they have size 1 so we can extend to 2 x 2 square, but it's wrong since the "top-left" corner is 0s which is not all solid 1s. We have to check if there is a "hole" in the "top-left" corner. We need to check the "top-left" corner as well to make sure the square is all solid 1s.
1, 1, 1
1, 0, 1 <- there is a "hole" so we can't extend to `3 x 3` square.
1, 1, ?Q: How to calculate the result? Based on the previous logic, we can calculate the result by checking the minimum of the 3 neighbors, and add 1 to it. We are limited by the minimum of the neighbors. For example:
- Left: A square of size
0. - Top: A square of size
1 - Top-Left: A square of size
1 - The result is
min(0, 1, 1) + 1 = 2
0, 1
1, ? -> minOf(0, 1, 1) + 1 = 2
1, 0, 1 1, 0, 1 1, 0, 1
1, 1, 1 -> 1, ?, ? -> 1, 1, 1
0, 1, 1 0, ?, ? 0, 1, 2We definitely can NOT form a 2 x 2 square, because there is a "hole" in the top-left corner. The rule is that we are only strong as our weakest link. Suppose the top and left is huge (size 100), but top-left is tiny (size 1), we can't form a size 101 square, the top-left gap breaks the chain, we are forced to be size min(100, 100, 1) + 1 = 2.
For more explanations, please see below Detailed Explanations.
Let dp[i][j] be the side length of the largest square whose bottom-right corner is at (i, j).
The state transition is:
- If cell is
'0', thendp[i][j] = 0, we can't be part of any square. - If cell is
'1', we look at the 3 neighbors: thetop-left corner(i-1, j-1), thetop edge(i-1, j), and theleft edge(i, j-1), thendp[i][j] = 1 + min(top-left, top, left), we can be part of the square with the side length of the minimum of the 3 neighbors. - Base case: for the first row and column, if the cell is
'1', thendp[i][j] = 1, because there is no top or left neighbor to expand.
fun maximalSquare(matrix: Array<CharArray>): Int {
val m = matrix.size
val n = matrix[0].size
var longestSide = 0
val dp = Array(m) { IntArray(n) }
for (i in 0 until m) {
for (j in 0 until n) {
dp[i][j] = if (matrix[i][j] == '0') 0
else if (i == 0 || j == 0) 1 // Base case
else {
minOf(dp[i - 1][j - 1],
dp[i - 1][j],
dp[i][j - 1]) + 1
}
longestSide = maxOf(longestSide, dp[i][j])
}
}
return longestSide * longestSide
}For the first row and first column, if there is a '1', the max square size is just 1 (because there are no Top or Left neighbors to extend).
// DP table after filling first row and first column:
[
[1, 1, 1],
[1, ?, ?],
[1, ?, ?]
]- Original cell is
1. - Neighbors:
- Top:
1 - Left:
1 - Top-Left:
1
- Top:
- Formula:
min(1, 1, 1) + 1 = 2 - We can form a square with side length 2 here.
[
[1, 1, 1],
[1, 2, ?],
[1, ?, ?]
]- Original cell is
1. - Neighbors:
- Top:
1(at(0, 2)) - Left:
2(at(1, 1)) - Top-Left:
1(at(0, 1))
- Top:
- Formula:
min(1, 2, 1) + 1 = 2 - Even though the Left is 2, the minimum is 1, so side length is 2.
[
[1, 1, 1],
[1, 2, 2],
[1, ?, ?]
]- Original cell is
1. - Neighbors:
- Top:
2(at(1, 2)) - Left:
2(at(2, 1)) - Top-Left:
2(at(1, 1))
- Top:
- Formula:
min(2, 2, 2) + 1 = 3 - We found a square of side 3.
[
[1, 1, 1],
[1, 2, 2],
[1, 2, 3]
]Throughout this process, we keep a variable called max_side. Each time we fill in a value in the DP table, if it is larger than our current max_side, we update it. In the example above, max_side becomes 3.
The question asks for the Area:
Result: 3 * 3 = 9
Q: If the
top-leftis different fromtopandleft, what does that mean and how does it affect the result?
The example, suppose we are at cell 1 and have 3 neighbors:
top:4(A large 4 x 4 square)left:4(A large 4 x 4 square)top-left:2(A small 2 x 2 square)
The result is min(2, 4, 4) + 1 = 3.
Why is the result 3, not 5? We have a large walls of size 4 on bother sides, but there is a hollow center if we connect them together.
The top-left is only 2, it means that there is a 0 (hole) in 3 steps back diagonally.
matrix: dp:
0 0
1 1
1 -> 2 T
? L ?Conclusion: If top-left is different (smaller) from top and left, it means that there is a hole somewhere diagonally that prevents you from expanding the two large top and left sides.