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

*I like to keep my brain sharp by working on programming puzzlers. On off weeks I'm going to start posting programming puzzlers I've collected over the years. Hopefully you'll find them as entertaining as I do.*

Another fun one that I enjoyed solving. As usual with these problems, there’s a fairly straightforward solution -- and a very efficient but harder to find solution.

### The Problem

Given a square 2D array of 1s and 0s, find the starting position (top left row, column) and size of the largest, solid square of 1s in the matrix. Try to find the most efficient (performance-wise) solution possible. The solution need not be memory constant, but should not modify the original data.

For example, if the matrix were:

0 0 0 0 0 0 0 0 0 0

0 0 0 0 1 1 0 0 0 0

0 0 0 0 1 1 0 0 0 0

0 0 0 1 1 0 0 0 0 0

0 0 0 1 1 1 1 0 0 0

0 0 0 0 0 1 1 1 0 0

0 0 0 0 0 1 1 1 0 0

0 0 0 0 1 1 1 1 0 0

0 0 0 0 0 0 1 0 0 0

0 0 0 0 0 0 1 0 0 0

The answer would be a square of size 3 at (row 5, column 5).

You may assume the following:

- The matrix is square (i.e.
*n x n*) - A lone 1 is a square of size 1.
- The square must be solid (no holes), but may be embedded in a larger, non-square shape.
- The rows and columns for the starting position are zero-indexed

### Spoiler Alert!

**Fair Warning:** there may be discussion of the problem and potential solutions posted in the comments below. Read at your own risk.

- Share This Post:
- Short Url: http://wblo.gs/gUJ

Print | posted on Monday, April 20, 2015 11:38 AM | Filed Under [ My Blog C# Software .NET Little Puzzlers ]

## Feedback

## # 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 ^_^