Practice Now
matrix algorithms
connected components
graph theory
computational geometry
adjacency matrix

Algorithm to find the total number of connected sets in a matrix

Data Structures & Algorithms practice on Codemia

Step through 300+ coding interview problems with animated visualisers that show the data structure changing as the code runs. The Blind 75 are free.

Practice algorithms
AlgorithmsData StructuresMath for Programmers

Introduction

Finding connected components in a binary matrix means counting the number of distinct groups of 1s that are connected horizontally, vertically, or diagonally. This is equivalent to counting connected components in a graph where each cell with value 1 is a node and adjacent cells are edges. The standard approach uses BFS or DFS, visiting each cell once for O(rows × cols) time complexity. Union-Find is an alternative that handles dynamic connectivity efficiently.

Problem Definition

 
1Input matrix:
21 0 0 1
31 1 0 0
40 0 1 1
50 1 0 0
6
7Connected components:
8Component 1: (0,0), (1,0), (1,1)
9Component 2: (0,3)
10Component 3: (2,2), (2,3)
11Component 4: (3,1)
12
13Answer: 4 connected sets

Two cells are connected if they are adjacent in any of the 8 directions (up, down, left, right, and 4 diagonals).

python
1def count_connected_components(matrix):
2    if not matrix or not matrix[0]:
3        return 0
4
5    rows, cols = len(matrix), len(matrix[0])
6    visited = [[False] * cols for _ in range(rows)]
7    count = 0
8
9    def dfs(r, c):
10        if r < 0 or r >= rows or c < 0 or c >= cols:
11            return
12        if visited[r][c] or matrix[r][c] == 0:
13            return
14        visited[r][c] = True
15        # Visit all 8 neighbors
16        for dr in [-1, 0, 1]:
17            for dc in [-1, 0, 1]:
18                if dr == 0 and dc == 0:
19                    continue
20                dfs(r + dr, c + dc)
21
22    for r in range(rows):
23        for c in range(cols):
24            if matrix[r][c] == 1 and not visited[r][c]:
25                dfs(r, c)
26                count += 1
27
28    return count
29
30# Example
31matrix = [
32    [1, 0, 0, 1],
33    [1, 1, 0, 0],
34    [0, 0, 1, 1],
35    [0, 1, 0, 0],
36]
37print(count_connected_components(matrix))  # 4

Time: O(rows × cols). Space: O(rows × cols) for visited array and recursion stack.

BFS avoids deep recursion, which matters for large matrices:

python
1from collections import deque
2
3def count_connected_bfs(matrix):
4    if not matrix:
5        return 0
6
7    rows, cols = len(matrix), len(matrix[0])
8    visited = [[False] * cols for _ in range(rows)]
9    count = 0
10    directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
11
12    for r in range(rows):
13        for c in range(cols):
14            if matrix[r][c] == 1 and not visited[r][c]:
15                # BFS from this cell
16                queue = deque([(r, c)])
17                visited[r][c] = True
18                while queue:
19                    cr, cc = queue.popleft()
20                    for dr, dc in directions:
21                        nr, nc = cr + dr, cc + dc
22                        if 0 <= nr < rows and 0 <= nc < cols and \
23                           not visited[nr][nc] and matrix[nr][nc] == 1:
24                            visited[nr][nc] = True
25                            queue.append((nr, nc))
26                count += 1
27
28    return count

Method 3: Union-Find (Disjoint Set Union)

Union-Find is efficient for dynamic connectivity and parallel processing:

python
1class UnionFind:
2    def __init__(self, n):
3        self.parent = list(range(n))
4        self.rank = [0] * n
5        self.count = 0
6
7    def find(self, x):
8        if self.parent[x] != x:
9            self.parent[x] = self.find(self.parent[x])  # Path compression
10        return self.parent[x]
11
12    def union(self, x, y):
13        px, py = self.find(x), self.find(y)
14        if px == py:
15            return
16        # Union by rank
17        if self.rank[px] < self.rank[py]:
18            px, py = py, px
19        self.parent[py] = px
20        if self.rank[px] == self.rank[py]:
21            self.rank[px] += 1
22        self.count -= 1
23
24def count_connected_union_find(matrix):
25    if not matrix:
26        return 0
27
28    rows, cols = len(matrix), len(matrix[0])
29    uf = UnionFind(rows * cols)
30
31    # Initialize: each 1-cell is its own component
32    for r in range(rows):
33        for c in range(cols):
34            if matrix[r][c] == 1:
35                uf.count += 1
36
37    # Union adjacent 1-cells
38    directions = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
39    for r in range(rows):
40        for c in range(cols):
41            if matrix[r][c] == 1:
42                for dr, dc in directions:
43                    nr, nc = r + dr, c + dc
44                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] == 1:
45                        uf.union(r * cols + c, nr * cols + nc)
46
47    return uf.count
48
49matrix = [
50    [1, 0, 0, 1],
51    [1, 1, 0, 0],
52    [0, 0, 1, 1],
53    [0, 1, 0, 0],
54]
55print(count_connected_union_find(matrix))  # 4

Time: O(rows × cols × α(n)) where α is the inverse Ackermann function (nearly constant).

4-Connected vs 8-Connected

The problem can define adjacency as 4-directional (no diagonals) or 8-directional (with diagonals):

python
1# 4-connected (horizontal and vertical only)
2directions_4 = [(-1,0), (1,0), (0,-1), (0,1)]
3
4# 8-connected (including diagonals)
5directions_8 = [(-1,-1), (-1,0), (-1,1), (0,-1), (0,1), (1,-1), (1,0), (1,1)]
6
7# Example where it matters:
8# 1 0
9# 0 1
10# 4-connected: 2 components (diagonal not connected)
11# 8-connected: 1 component (diagonal IS connected)

In-Place Modification (No Extra Space)

If you can modify the input matrix, mark visited cells by setting them to 0:

python
1def count_connected_inplace(matrix):
2    rows, cols = len(matrix), len(matrix[0])
3    count = 0
4
5    def dfs(r, c):
6        if r < 0 or r >= rows or c < 0 or c >= cols or matrix[r][c] == 0:
7            return
8        matrix[r][c] = 0  # Mark as visited
9        for dr in [-1, 0, 1]:
10            for dc in [-1, 0, 1]:
11                if dr == 0 and dc == 0:
12                    continue
13                dfs(r + dr, c + dc)
14
15    for r in range(rows):
16        for c in range(cols):
17            if matrix[r][c] == 1:
18                dfs(r, c)
19                count += 1
20
21    return count
22# Space: O(1) extra (excluding recursion stack)

C++ Implementation

cpp
1#include <vector>
2#include <queue>
3using namespace std;
4
5int countComponents(vector<vector<int>>& matrix) {
6    int rows = matrix.size(), cols = matrix[0].size();
7    int count = 0;
8    int dx[] = {-1,-1,-1,0,0,1,1,1};
9    int dy[] = {-1,0,1,-1,1,-1,0,1};
10
11    for (int r = 0; r < rows; r++) {
12        for (int c = 0; c < cols; c++) {
13            if (matrix[r][c] == 1) {
14                count++;
15                queue<pair<int,int>> q;
16                q.push({r, c});
17                matrix[r][c] = 0;
18                while (!q.empty()) {
19                    auto [cr, cc] = q.front(); q.pop();
20                    for (int d = 0; d < 8; d++) {
21                        int nr = cr + dx[d], nc = cc + dy[d];
22                        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols
23                            && matrix[nr][nc] == 1) {
24                            matrix[nr][nc] = 0;
25                            q.push({nr, nc});
26                        }
27                    }
28                }
29            }
30        }
31    }
32    return count;
33}

Common Pitfalls

  • Stack overflow with DFS on large matrices: Recursive DFS on a 1000×1000 matrix of all 1s creates up to 1,000,000 recursive calls, exceeding the default stack size. Use BFS (iterative) or increase the stack limit for large inputs.
  • Forgetting diagonal neighbors: If the problem requires 8-connectivity (including diagonals), checking only 4 directions undercounts components. Always clarify whether diagonal adjacency counts.
  • Marking visited after enqueuing in BFS: Mark cells as visited when you add them to the queue, not when you process them. Otherwise, the same cell gets added multiple times, wasting time and potentially causing duplicates.
  • Modifying the matrix when it should be preserved: The in-place approach destroys the input. If you need the original matrix later, use a separate visited array or make a copy first.
  • Off-by-one in boundary checks: Ensure nr >= 0 && nr < rows && nc >= 0 && nc < cols checks are correct. Using <= instead of < for the upper bound accesses out-of-bounds memory (C/C++) or throws IndexError (Python).

Summary

  • Use BFS or DFS to count connected components: visit each 1-cell, flood-fill its component, increment count
  • Time complexity: O(rows × cols) — each cell visited at most once
  • DFS is simpler to code; BFS avoids stack overflow on large matrices
  • Union-Find is useful for dynamic connectivity or parallel processing
  • Choose 4-connected or 8-connected based on the problem definition (diagonal adjacency)
  • This is equivalent to "Number of Islands" (LeetCode 200) with 4-connectivity
Related reading
Course
Intermediate
27 lessons
15 hours
DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course
Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300+ coding interview problems with animated visualisers that show the data structure changing as the code runs. The Blind 75 are free.

Practice algorithms
Codemia
© 2026 Codemia
Resources
Legal
Social
All Rights Reserved.