Count Square Submatrices

Today we are going to looking at another dynamic programming problem.

So one possibility to solve this would be to traverse through this matrix and at each index check to see if there is a square that begins from this current point. This won’t be efficient though because we will be checking the same values over and over.

For example, we will need to check the value of [0,1] for a square that starts at [0,0]. Then we will have to check it again when our square starts at [0,1]. You can see there will be a lot of repeats that we will check.

Ideally we will save the information we find out as we move through our matrix. How can we do this? Well at each index we can find out if this point is the end of a square. If it is then we can add this square to the previous number of squares that we already found.

For example:

We can see easily there will be 5 squares. 1 at each of the 4 points and then 1 more from the whole matrix. Now how do we use what we’ve seen? We move through our matrix and at every point we need to check its value and add it to a count (if the number is 0 then we can skip this point because it cannot create a square and does not add to our count).

We see the point at [0,0] is 1 so we will add 1 to our count. We move over to [0,1] and see its a 1, we add 1 to our count bringing us to 2. Now that we have reached the second row things get more interesting. Remember I said we need to find the points where they represent the END of a square. A point that is on the first row can be an individual square but it can’t be the END of a square. As well, a point that is in the first column (such as [1,0]), also cannot be the END of a square. We check position [1,1], it is a 1, so we increase our count to 3.

For every other point that is not in the first row or is not in the first column we will check to see if this is an END of a square. This means we need to check the positions of [0,0], [0,1], and [1,0]. What would happen if [0,0] = 0. We would no longer have our fifth square, and we know this because we see a zero. So this means we want to add the minimum value out of our 3 points we check. In our case every point = 1, so our minimum is 1.

We check our point at [1,1], we see it has a 1 so we add another to our count, which is now 4. THEN we add the minimum of the 3 points we checked, which is 1. 4 + 1 = 5 and there are our 5 squares. In this scenario we are finished traversing our matrix, but the idea is if the matrix were larger, then we need would update the position [1,1] = 2. This means that when this point is checked by preceding points it knows how many squares this point has been a part of.

Lets see the code in action: