**Given a matrix with 1s and 0s, please find the number of groups of 1s. A group is defined by horizontally or vertically adjacent 1s. For example, there are four groups of 1s in Figure 1 which are drawn with different colors.**

__Problem:__Figure 1: A matrix with four groups of 1s. Different groups are drawn with different colors. |

**All numbers in the matrix are scanned one by one. When a 1 is met, a group of 1s has been found, and then all 1s in the group are flipped to 0s.**

__Analysis:__Figure 2: The new matrix after all 1s in the first group (in the red boundary) have been flipped |

Therefore, the overall function to count the groups of 1s in
a matrix can be implemented in the following C++ code:

int groupOf1(int* nums, int rows, int cols){

if(nums == NULL || rows <= 0 || cols <= 0)

return 0;

int group = 0;

for(int i = 0; i <
rows * cols; ++i){

if(nums[i] == 1)

{

group++;

flipAdjacent1(nums, rows, cols, i);

}

}

return group;

}
Let’s move on to flip 1s inside a group. Actually, it is an
application of the seed
filling algorithm. When we are going to flip a group starting from an
entry, we take the entry as a seed and push it into a stack. At each step, we
get an entry from the top of the stack, flip it, and then push its neighboring
entries into the stack. The process continues until the stack is empty. The
following code implements this algorithm:

void flipAdjacent1(int* nums,
int rows, int
cols, int index){

stack<int> group;

group.push(index);

while(!group.empty())

{

int topIndex = group.top();

group.pop();

nums[topIndex] = 0;

int row = topIndex / cols;

int col = topIndex % cols;
// up

if(row > 0 && nums[(row - 1) * cols + col]
== 1)group.push((row - 1) * cols + col);

// right

if(col < cols - 1 && nums[row * cols + col + 1] == 1)

group.push(row * cols + col + 1);

// down

if(row < rows - 1 && nums[(row + 1) * cols + col] == 1)

group.push((row + 1) * cols + col);

// left

if(col > 0 && nums[row * cols + col - 1] == 1)

group.push(row * cols + col - 1);

}

}

More coding interview questions are discussed in my book <Coding Interviews: Questions, Analysis & Solutions>. You may find the details of this book on Amazon.com, or Apress.

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.

it is simple DFS..

ReplyDeleteYou don't use a data structure to do DFS, that is one of the biggest advantages of DFS over BFS.

ReplyDeleteWithout ANY data structure, how can you go back in DFS? You can't. Recursive calling is also using program stack to keep track, and it is slower than using an iterative solution with a stack for just keeping track of nodes, instead of function calls.

DeleteHi, Since you are going from left to right is it really necessary for you to flip 1s on the left and flip 1s in the top row. Wouldn't they have been taken care of already ? Shouldn't it be sufficient to flip 1s to the right and bottom ?

ReplyDeleteNo frog. Consider the following matrix:

Delete0 0 0 1 0

0 1 1 1 0

1 1 1 1 1

I tried to implement it in java without modifying the input array.

ReplyDeleteBelow is the code. Please give your input. I am traversing through each element once .

If current element is one && previous element in same row or in same column is not one then increment groupCount

else traverse to next element.

public int numberOfGroups(int matrix[][])

{

int groupCount=0;

boolean previousOne =false;

for (int row = 0 ; row < matrix.length; row++)

{

previousOne=false;

for (int col=0 ;col=0 && matrix[row-1][col]==1) || ((col-1)>=0 && matrix[row][col-1]==1 ) ) )

{

groupCount++;

}

}

else if (matrix[row][col]==0)

{

previousOne=false;

}

}

}

return groupCount;

}

import java.util.HashMap;

ReplyDeletepublic class matrixGroups

{

static int[][] tab={{1,1,0,0,1}, {1,0,0,1,0}, {1,0,0,1,0}, {0,1,1,0,0}};

static int elementInGroup=1;

static HashMap grps=new HashMap();

static int groupsCount=0;

public static void main(String[] args)

{

for(int iRow=0;iRow<4;iRow++)

{

for(int iCol=0;iCol<5;iCol++)

{

if(tab[iRow][iCol]==elementInGroup)

{

System.out.println(iRow+"-"+iCol);

getAdjacentOnes(iRow,iCol);

}

}

}

System.out.print(groupsCount+" Groups "+grps.toString());

}

static void getAdjacentOnes(int r,int c)

{

String current=r+"x"+c;

String top=(r-1)+"x"+c;

String left=r+"x"+(c-1);

if(r>0)

{

if(tab[r-1][c]==elementInGroup)

if(grps.containsKey(top))//group already created

grps.put(current,grps.get(top));

else //create new group

{

groupsCount++;

grps.put(top,groupsCount);

grps.put(current,groupsCount);

}

}

if(c>0)

{

if(tab[r][c-1]==elementInGroup)

if(grps.containsKey(left))//group already created

grps.put(current,grps.get(left));

else //create new group

{

groupsCount++;

grps.put(left,groupsCount);

grps.put(current,groupsCount);

}

}

}

}

simple dfs question count how many time connected components are there

ReplyDelete