Microsoft Online Assessment Interview Question: Count Connected Components in a Binary Matrix

Count Connected Components in a Binary Matrix

Given a binary matrix, count the number of connected components formed by the cells with value 1. Cells are connected if they are adjacent vertically or horizontally.

For example:

1 0 1 0
0 0 2 0
0 0 0 0
0 0 0 0

and

2 0 0 1 0
0 0 0 0 0
0 2 0 0 1
0 0 0 0 0
1 0 2 0 0

This problem asks you to count connected components in a grid by treating valid cells as graph nodes and linking them through four-directional adjacency. A standard solution is to scan the matrix, start a DFS or BFS from each unvisited target cell, and mark the entire component as visited while incrementing the answer once. The approach is simple, efficient, and runs in O(mn) time.