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]]	3	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

Visualization Player

Solution❯

Understanding the Problem

We are given a binary matrix, where each cell contains either 0 or 1. Our task is to count how many connected components of 1s exist in this matrix.

A connected component is a group of 1s that are connected horizontally or vertically. Diagonal connections do not count. Two 1s are part of the same component if you can reach one from the other by moving up, down, left, or right through other 1s.

Step-by-Step Solution with Example

step 1: Understand the input

We will be given a 2D array (matrix) of 0s and 1s. Each cell represents either land (1) or water (0).

step 2: Prepare for traversal

We need to track whether a cell has already been visited so that we don’t count the same component more than once. We'll use a separate matrix or a set to mark visited cells.

step 3: Traverse the matrix

Loop through each cell in the matrix. If the cell contains a 1 and has not been visited, that means it’s a new component. We then perform a traversal (DFS or BFS) starting from that cell.

step 4: Use DFS to mark connected 1s

From the current cell, we explore all its 4-directionally adjacent neighbors. For every neighbor that is also 1 and unvisited, we continue the traversal. This way, we mark the entire component as visited.

step 5: Count the components

Every time we start a new DFS from an unvisited 1, it means we’ve found a new component. So, we increment our count.

step 6: Example

Let’s walk through this:

The group of 1s at the top-left ((0,0), (0,1), (1,1)) form one component.
The group (1,3), (2,3) is another component.
The cell (3,0) is a standalone 1, which is its own component.

So the total number of components is 3.

Edge Cases

Empty matrix

If the matrix is empty or has no rows/columns, there are no components. Return 0.

All zeros

If every cell is 0, then again, no components exist. Output is 0.

Single cell matrix

If the matrix is [[1]], output is 1. If it is [[0]], output is 0.

Diagonal connections

If 1s are connected only diagonally, they are not considered part of the same component.

Finally

This problem helps build intuition for graph traversal using DFS or BFS. It also teaches how to treat a 2D matrix as a graph, where each cell is a node. By following a systematic approach — identifying a fresh 1, traversing its full component, and marking visited nodes — we ensure accurate counting and avoid revisiting nodes. Always consider edge cases to make the solution complete and robust.

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

Comments

Loading comments...