Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.
Example 1:
Input: matrix = [ [0,1,1,1], [1,1,1,1], [0,1,1,1] ] Output: 15 Explanation: There are 10 squares of side 1. There are 4 squares of side 2. There is 1 square of side 3. Total number of squares = 10 + 4 + 1 = 15.
Example 2:
Input: matrix = [ [1,0,1], [1,1,0], [1,1,0] ] Output: 7 Explanation: There are 6 squares of side 1. There is 1 square of side 2. Total number of squares = 6 + 1 = 7.
Constraints:
1 <= arr.length <= 3001 <= arr[0].length <= 3000 <= arr[i][j] <= 1
The description was taken from https://leetcode.com/problems/count-square-submatrices-with-all-ones/.
#O(M*N) Time, O(M*N) Space
class Solution(object):
def countSquares(self, matrix): m, n = len(matrix), len(matrix[0]) dp = matrix.copy()
output = 0
for col in range(n):
output += dp[0][col]
for row in range(1, m):
output += dp[row][0]
for row in range(1, m):
for col in range(1, n):
if dp[row][col]:
dp[row][col] = min(matrix[row][col-1], matrix[row-1][col-1], matrix[row-1][col]) + 1
output += dp[row][col]
return outputThis problem is a variation of Maximal Square.
If the problem asked for the greatest island, we'd be able to solve this with a Depth-First Search.
The problem with a square is we could calculate the greatest four sides of the square but it would be possible that there would be zeros within the boundaries that would nullify it which we wouldn't be able to easily track if we did a traditional search.
To solve this, we are going to have to continuously track the greatest square length up to each current cell, this is a Dynamic Programming method.
By tracking the greatest square length up until each current cell, if we come across a one, we'll be able to just look for the smallest square length from each top, top-left, and left neighbors, since a square has to have an even length of sides, its area will be dependent on the smallest side.
If for example, we have this square in the matrix:
| 1 | 0 |
| 1 | 1 |
The minimum side is one, so we wouldn't be able to form a square from that greater than an area of one.
If we had this square:
| 1 | 1 |
| 1 | 1 |
The minimum side is two, so we would be able to make a square with an area of four. We may also notice that we aren't increasing square sizes until we get to the bottom-right side of them. This allows us to not double-count.
Once we finish traversing the matrix, we'll just need to do is return the sum of all the values that we incremented. This will give us a breakdown of sizes similar to the explanation from the problem description.
Let's start by saving the length and width of the matrix to values m, and n, so that we don't have to keep rewriting these later.
m, n = len(matrix), len(matrix[0])
We'll also want to make a copy of the matrix to build off of.
Technically we could perform this algorithm in place, but it's generally best practice to not do that for concurrency reasons.
dp = matrix.copy()
We'll also create a running sum that we'll be outputting.
output = 0
For the top row and left column of the matrix, it would be impossible for these values to be the bottom-right corner of any square greater than one.
We'll go through and increment the output by all of these one-side squares.
for col in range(n):
output += dp[0][col]
for row in range(1, m):
output += dp[row][0]
Once we have done that, we can begin our search from the second row and column.
for row in range(1, m):
for col in range(1, n):
If the current cell is a one then we will try this position as the bottom-right of a square.
We'll get the minimum of the three neighboring values and add a one to it.
if dp[row][col]:
dp[row][col] = min(matrix[row][col-1], matrix[row-1][col-1], matrix[row-1][col]) + 1
Once we have done that, we'll increment the output by this value.
It will either stay a one if the surrounding neighbors didn't make up a square, or it will be a greater side to a square if it did.
output += dp[row][col]
When we have summed all of these square sides, we'll return the output.
return output