Connected Components in a Matrix - Visualization

Graphs

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

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

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

1 1 0 0
0 1 0 1
0 0 0 1
1 0 0 0

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❯

  1. Initialize a visited matrix of the same size as the input matrix, filled with false.
  2. Define DFS or BFS to explore connected 1s from a given starting cell.
  3. Loop through each cell in the matrix:
    1. If the cell has value 1 and is not visited:
      1. Increment the component counter.
      2. Call DFS/BFS to mark all reachable 1s from this cell.
  4. Return the total number of components found.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#define ROWS 4
#define COLS 4

int visited[ROWS][COLS];
int matrix[ROWS][COLS] = {
  {1, 1, 0, 0},
  {0, 1, 0, 0},
  {1, 0, 0, 1},
  {0, 0, 1, 1}
};

void dfs(int r, int c) {
  if (r < 0 || c < 0 || r >= ROWS || c >= COLS || visited[r][c] || matrix[r][c] == 0) return;
  visited[r][c] = 1;
  int dr[] = {0, 1, 0, -1};
  int dc[] = {1, 0, -1, 0};
  for (int i = 0; i < 4; i++) {
    dfs(r + dr[i], c + dc[i]);
  }
}

int main() {
  int components = 0;
  for (int i = 0; i < ROWS; i++) {
    for (int j = 0; j < COLS; j++) {
      if (matrix[i][j] == 1 && !visited[i][j]) {
        components++;
        dfs(i, j);
      }
    }
  }
  printf("%d\n", components);
  return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(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 CaseO(m * n)Each cell is visited once; for every new component, we run DFS/BFS from the unvisited 1.
Worst CaseO(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.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...