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 |
  • submit to reddit

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.

 

Comments

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
  }
}

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.