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.