Coding Interview Questions: 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.
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.
int groupOf1(int* nums, int rows, int cols)
{
if(nums == NULL || rows <= 0 || cols <= 0)
return 0;
{
if(nums[i] == 1)
{
group++;
flipAdjacent1(nums, rows, cols, i);
}
}
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;
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);
}
}
Read full article from Coding Interview Questions: 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.
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.
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;
}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);
}
}
Read full article from Coding Interview Questions: No. 41 - Group of 1s in a Matrix
