Wednesday, February 20, 2013

No. 41 - Group of 1s in a Matrix

Problem: 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.
Figure 1: A matrix with four groups of 1s. Different groups are drawn with different colors.

Analysis: 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.
For example, the first entry in the matrix of Figure 1 contains 1, so the first group of 1s is found when we access to the first entry. After all 1s in the group have been flipped to 0s, the matrix becomes the one in Figure 2.
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.

15 comments:

  1. Replies
    1. Hi Harry,

      Your 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

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

    ReplyDelete
    Replies
    1. Without 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.

      Delete
    2. Hi Harry,

      Your 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

      Delete
  3. 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 ?

    ReplyDelete
    Replies
    1. No frog. Consider the following matrix:

      0 0 0 1 0
      0 1 1 1 0
      1 1 1 1 1

      Delete
  4. I tried to implement it in java without modifying the input array.
    Below 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;
    }

    ReplyDelete
  5. import java.util.HashMap;
    public 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);
    }
    }
    }
    }

    ReplyDelete
  6. simple dfs question count how many time connected components are there

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

    ReplyDelete
  8. Hello There,


    I 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

    ReplyDelete
  9. Hiya,


    Fully 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

    ReplyDelete
  10. Hi Mate,


    11/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

    ReplyDelete