James Michael Hare

...hare-brained ideas from the realm of software development...
posts - 166 , comments - 1431 , trackbacks - 0

My Links

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.

Blogs I Read

Follow BlkRabbitCoder on Twitter

Tag Cloud

Archives

Post Categories

.NET

CSharp

Little Wonders

Little Wonders

vNext

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.

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

Powered by: