I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

# Thursday Code Puzzler: Matrix Search

05.02.2013
| 3435 views |

Thursday is code puzzler day here at DZone. The idea is simple: solve the coding problem as efficiently as you can, in any language or framework that you find suitable.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

Do you have code puzzlers that you'd like to share with the DZone community?  If so, please submit here.

Matrix Search

Given a matrix of 1s and 0s, write an algorithm that will find the groups of 1s. A group is a series of 1's that are connected in any direction. An example matrix would look as follows, defined as a 2d array of integers

```10111000
10110001```

Catch up on all our previous puzzlers here.

Tags:

### Andrew Gilmartin replied on Thu, 2013/05/02 - 7:21am

Can the group have holes? For example, is this

```1 1 1
1 0 1
0 1 0
```
one group, ie
```a a a
a   a
a
```
or two, ie
```a a a
a   a
b
```
-- Andrew

### Niranjan Tallapalli replied on Thu, 2013/05/02 - 9:07am

There might be better time complexity than what I have written but here is my approach, I have also blogged this solution on my blog

```int findMaxDepth(int[][] n, boolean[][] bool, int i, int j) {
// Check if i, j (indexes) are within the size of array
// Check if the cell is already traversed or not using bool array
// Check if the cell value is 1 before counting it as part of a sector
if(i >= 0 && i < n.length &&                  j >=0 && j < n[0].length
&& bool[i][j] != true && n[i][j] != 0) {
currentDepth++;

// Mark the status of the cell for backtracking purpose
bool[j] = true;

// left traversal
findMaxDepth(n, bool, i-1, j);
// right traversal
findMaxDepth(n, bool, i+1, j);

// top traversal
findMaxDepth(n, bool, i, j-1);
// bottom traversal
findMaxDepth(n, bool, i, j+1);

// Top-Bottom diagnol
// diagnol-down traversal
findMaxDepth(n, bool, i+1, j+1);
// diagnol-up traversal
findMaxDepth(n, bool, i-1, j-1);

// Bottom-Top diagnol
// diagnol-down traversal
findMaxDepth(n, bool, i+1, j-1);
// diagnol-up traversal
findMaxDepth(n, bool, i-1, j+1);
}
return currentDepth;
}```

### Ben Ritchie replied on Thu, 2013/05/09 - 7:18pm

```// our provided matrix
var matrix[int][int]

// Define a new matrix rowstripsize[int][int] is either 0 or an int representing number of horizontal neighbours - on this row or above - connected to this matrix index i,j containing a 1
var rowstripsize[int][int]

computeGroups(matrix) {

// populate rowstripsize
for (int i = 0; i<matrix.height-1; i++) {
populateRowSizes(i)
}

maxGroupSize = 0

// easily build reports on groups
for (cell : rowstripsize) {
maxGroupSize = max(maxGroupSize, cell)
}

print "max group size is " + maxGroupSize
}

// populate rowstripsizes for a row
populateRowSizes(int i) {

var seriesOfOnes = 0

for(int j =0; j< matrix.width-1; j++) {
if (matrix[i][j] = 1) { // another one - possibly first
seriesOfOnes ++
} else if (seriesOfOnes > 0) { // end of a run of 1s - fill in stripsize in rowstripsize
fillInStripSize(i, j, seriesOfOnes)
// reset counter
seriesOfOnes = 0
} else {
// do nothing its a lone zero
}
}
}

// update rowstripsize for this strip considering stripsizes above
fillInStripSize(int i, int finalOne, int seriesOfOnes) {

// if cells above our strip have a strip size then we should add it to our group total
// in large matrices there may be muliple strips above our strip! So only count new strips
var stripAboveCounted = false

// our grand total for this strip so far
var totalGroupSizeSoFar = seriesOfOnes

//
// Add all unique stripsizes above, including those connected by diaganols
//
// So define the start and end index..

var aboveStartSearchIndex = finalOne - seriesOfOnes;
// allow for diagonols by trying going back one in above strip search
aboveStartSearchIndex = max(0, aboveStartSearchIndex - 1);

// allow for diagonols by trying going fwd one in above strip search
var aboveEndSearchIndex = min(matrix.width, finalOne + 1);

// Now we can add up the unique stripssizes connected to this strip above
for (int j=aboveStartSearchIndex; j <= aboveEndSearchIndex; j++) {
var stripSizeAbove = rowstripsize[i-1][j]

if (stripSizeAbove > 0 && !stripAboveCounted) {
totalGroupSizeSoFar += stripSizeAbove
stripAboveCounted = true
} else if (stripSizeAbove = 0 && stripAboveCounted) {
stripAboveCounted = false
}
}

// Now we know the grand total for this strip - populate it
for (int j=finalOne - seriesOfOnes; j <= finalOne; j++) {
rowstripsize[i][j] = totalGroupSizeSoFar
}
}
```