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.

8 comments:

  1. 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, 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
  3. 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
  4. 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
  5. simple dfs question count how many time connected components are there

    ReplyDelete