# James Michael Hare

...hare-brained ideas from the realm of software development...

### News

Welcome to my blog! I'm a Sr. Software Development Engineer in the Seattle area, who has been performing C++/C#/Java development for over 20 years, but have definitely learned that there is always more to learn!

All thoughts and opinions expressed in my blog and my comments are my own and do not represent the thoughts of my employer.

## 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 00 0 0 0 1 1 0 0 0 00 0 0 0 1 1 0 0 0 00 0 0 1 1 0 0 0 0 00 0 0 1 1 1 1 0 0 00 0 0 0 0 1 1 1 0 00 0 0 0 0 1 1 1 0 00 0 0 0 1 1 1 1 0 00 0 0 0 0 0 1 0 0 00 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