Connected Components in a Matrix

Problem Statement❯

The Connected Components in a Matrix problem involves identifying clusters of connected 1s in a binary matrix. Two 1s are considered connected if they are adjacent vertically or horizontally (not diagonally).

The task is to count how many such distinct connected groups (components) exist in the matrix.

Examples❯

Matrix	Connected Components	Description
[[1,1,0,0],[0,1,0,0],[1,0,0,1],[0,0,1,1]]	2	Two distinct groups of connected 1s
[[1,0,0],[0,0,0],[0,0,1]]	2	Two isolated 1s not connected
[[1,1],[1,1]]	1	All 1s form one connected block
[[0,0],[0,0]]	0	No 1s, hence no components
[[1]]	1	Single cell with 1 is its own component

Solution❯

What is a Connected Component?

In a binary matrix (where cells are either 0 or 1), a connected component is a group of adjacent cells with the value 1 that are connected either vertically or horizontally (not diagonally). For example, a group of 1s forming a block or line can be considered one connected component if each 1 can be reached from another through a sequence of adjacent 1s.

Empty or All-Zero Matrix

If the input matrix is empty or all its cells are 0, then there are no connected components of 1s. The result will be 0.

Single Cell Matrix

If the matrix has only one cell and it's a 1, then there's exactly 1 connected component. If it's 0, then there are 0 components.

Typical Case

In a normal matrix with a mix of 0s and 1s, we scan each cell. When we find a 1 that hasn’t been visited yet, we launch a DFS or BFS to mark all the 1s in that group. We increase the component count by 1 for each such discovery. For example:

1 1 0
0 1 0
0 0 1

In this matrix, the top-left 3 ones are connected and form one component, while the bottom-right one is isolated and forms another. So the answer is 2.

Why Use DFS or BFS?

DFS and BFS help traverse all adjacent 1s from a starting cell efficiently. Without them, it would be hard to explore all cells in the component without revisiting or missing some.

Algorithm Steps❯

Initialize a visited matrix of the same size as the input matrix, filled with false.
Define DFS or BFS to explore connected 1s from a given starting cell.
Loop through each cell in the matrix:

If the cell has value 1 and is not visited:

Increment the component counter.
Call DFS/BFS to mark all reachable 1s from this cell.

Return the total number of components found.

Code

JavaScript

function countConnectedComponents(matrix) {
  const rows = matrix.length;
  const cols = matrix[0].length;
  const visited = Array.from({ length: rows }, () => new Array(cols).fill(false));
  let components = 0;

  const directions = [
    [0, 1], [1, 0], [0, -1], [-1, 0] // right, down, left, up
  ];

  function dfs(r, c) {
    if (
      r < 0 || c < 0 || r >= rows || c >= cols ||
      visited[r][c] || matrix[r][c] === 0
    ) return;
    visited[r][c] = true;
    for (const [dr, dc] of directions) {
      dfs(r + dr, c + dc);
    }
  }

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (matrix[i][j] === 1 && !visited[i][j]) {
        components++;
        dfs(i, j);
      }
    }
  }

  return components;
}

console.log(countConnectedComponents([
  [1,1,0,0],
  [0,1,0,0],
  [1,0,0,1],
  [0,0,1,1]
])); // Output: 2

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(m * n)	Every cell in the matrix must be visited at least once to ensure no 1s are missed, even if all values are 0.
Average Case	O(m * n)	Each cell is visited once; for every new component, we run DFS/BFS from the unvisited 1.
Worst Case	O(m * n)	In the worst case, the matrix is filled with 1s, and every cell is part of a single large component traversed by DFS/BFS.

Space Complexity❯

O(m * n)

Explanation: A visited matrix of the same size is used to keep track of explored cells.

⬅ Previous TopicNumber of Provinces in an Undirected Graph

Next Topic ⮕Rotten Oranges Problem - BFS in Matrix