**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..

ReplyDeleteHi Harry,

DeleteYour blog is such a complete read. I like your approach with No. 41 - Group of 1s in a Matrix have the same set of integers. Clearly, you wrote it to make learning a cake walk for me.

We're currently in an infinite loop between sales and support, neither of whom seem to be able to understand a basic issue. This enables the industry to summon command without putting in the infrastructure at all AWS Training . AWS has several configuration management solutions for AWS scalability, flexibility, availability and management.

We want to purchase some sizeable reserved instances but are told that the only way to pay is all at once with a credit card. No split payments, no offer to pay by check, no offer to pay by ACH, no offer to pay by wire.

Can someone explain to me how AWS serves enterprises if they only accept consumer methods of payment?

Super likes !!! for this amazing post. I thinks everyone should bookmark this.

Kind Regards,

Kevin

You 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 Harry,

DeleteYour writing shines like gold! There is no room for gibberish here clearly. You nailed it in No. 41 - Group of 1s in a Matrix!

I will have the mp3 files my customer buys on a WordPress page and a cart will < direct them to that page AWS Training USA . If I want the mp3 files to be downloaded by the customer is there any reason to protect them except to keep them from being indexed by a search engine? Do I need to have a key or do a get operation other than have server-side encryption in S3?

Very useful article, if I run into challenges along the way, I will share them here.

Grazie,

Kevin

Hi, 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

ReplyDeleteJust use bit AND for 1's and bit OR for 0's. Operating row-wise then column-wise.

ReplyDeleteHello There,

ReplyDeleteI am shocked, shocked, that there is such article exist!! But I really think you did a great job highlighting some of the key Group of 1s in a Matrix in the entire space.

I am a freelancer and I previously created an account using a Gmail address and obtained my certification with this account. During the registration process of the APN program it needs a non Gmail address so I used my professional address, how can I merge or link the certifications of my first account with the APN program?

Super likes !!! for this amazing post. I thinks everyone should bookmark this.

Thanks a heaps,

Abhiram

Hiya,

ReplyDeleteFully agree on No. 41 - Group of 1s in a Matrix . We’re seeing a lot of projects tackle big complex problems but few seem to have taken into consideration and in particular reasons to adopt. AWS Training USA

I have a simple site that as an S3 static front end and a simple backend in lambda.The backend processes frontend forms. All it does is put the data in a database and sends an email to the administrator.

Once again thanks for your tutorial.

Grazie,

Radhey

Hi Mate,

ReplyDelete11/10!! Your blog is such a complete read. I like your approach with No. 41 - Group of 1s in a Matrix. Clearly, you wrote it to make learning a cake walk for me AWS Training

We're currently in an infinite loop between sales and support, neither of whom seem to be able to understand a basic issue.

We want to purchase some sizeable reserved instances but are told that the only way to pay is all at once with a credit card. No split payments, no offer to pay by check, no offer to pay by ACH, no offer to pay by wire. AWS Training USA

Can someone explain to me how AWS serves enterprises if they only accept consumer methods of payment?

Super likes !!! for this amazing post. I thinks everyone should bookmark this.

Kind Regards,

Radhey