James Michael Hare

# re: Little Puzzlers–Largest Square of ‘1’s in a Matrix

Another variation on this is to find the minimum number of squares. This is used in determining sheet resistance in electronic design. Eevblog post a video on Youtube about it recently.

# re: Little Puzzlers–Largest Square of ‘1’s in a Matrix

My "sketch" of a plan is based on the idea that any particular cell containing a `1` is the bottom right corner of a square. We can determine how large that square is by considering the cells immediately left, immediately above, and immediately above-left, finding out how large a square they were part of, taking the minimum of that and adding 1.

We don't need to keep all of this information around - if we were row-wise, then all we need to know is what size squares appeared in the previous row, plus the values we've computed in the current row. We also track the largest square we've yet seen and where is was.

<pre>
currentRow[] = {0}, largestSeen = 0, largestCol = 0, largestRow = 0

for(row = 0;row < n;row++)
{
previousRow[] = currentRow
currentRow[] = {0}
for(col = 0;col<n;col++)
{
squareSize = 0
if(mat(row,col) = 1)
{
squareSize = 1 + Min (
col == 0 ? 0 : currentRow[col-1],
col == 0 ? 0 : previousRow[col-1],
previousRow[col])
currentRow[col] = squareSize
if(squareSize > largestSeen)
{
largestSeen = squareSize
largestCol = col
largestRow = row
}
}
}
}
</pre>

Admittedly, this finds the bottom right of the square rather than top left.

Does this work? It seems to, but I've only put about 20 minutes thought into it.

# re: Little Puzzlers–Largest Square of ‘1’s in a Matrix

Minor typographical corrections to the above, no change to the planned algorithm at the moment:

if we were row-wise == if we WORK row-wise
and where is was. == and where it was.

And I was going to point out after admitting that we find the bottom-right corner that its just very simple maths to compute top-left from those values.

# re: Little Puzzlers–Largest Square of ‘1’s in a Matrix

You should publish a unit test suite for your puzzlers :-)

# re: Little Puzzlers–Largest Square of ‘1’s in a Matrix

Here's a Javascript implementation:
http://pastebin.com/kvr3SDZX

It takes a copy of the matrix, then iterates in reverse from the bottom right tp top left corners determining how big the square is at each element by looking at three previously visited nearby elements.

Each time a larger square is found it keeps track of that position so eventually it finds the largest square closest to the top/left.

# re: Little Puzzlers–Largest Square of ‘1’s in a Matrix

To Damien's algorithm, since immediately above and immediately left both take into account immediately above-left, you shouldn't have to consider it for the current cell.

# re: Little Puzzlers–Largest Square of ‘1’s in a Matrix

@jswolf - consider the following layout, and be considering the bottom right square:

0 1 1
1 1 1
1 1 1 <-- We're considering this cell

The square immediately above is the bottom-right corner of a 2x2 square, as is the square immediately left. However, this square is the base of a 2x2 square, not a 3x3, because the square above-left of here is the bottom-right of a 1x1 square, not a 2x2.

# re: Little Puzzlers–Largest Square of ‘1’s in a Matrix

@Damien, thanks for the counter-example ^_^