Connected Components in a Matrix

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.

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.

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.

#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;
}

#include <iostream>
#include <vector>
using namespace std;

void dfs(int r, int c, vector<vector<int>>& matrix, vector<vector<bool>>& visited) {
  int rows = matrix.size(), cols = matrix[0].size();
  if (r < 0 || c < 0 || r >= rows || c >= cols || visited[r][c] || matrix[r][c] == 0) return;
  visited[r][c] = true;
  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], matrix, visited);
  }
}

int main() {
  vector<vector<int>> matrix = {
    {1, 1, 0, 0},
    {0, 1, 0, 0},
    {1, 0, 0, 1},
    {0, 0, 1, 1}
  };
  int rows = matrix.size(), cols = matrix[0].size(), components = 0;
  vector<vector<bool>> visited(rows, vector<bool>(cols, false));
  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, matrix, visited);
      }
    }
  }
  cout << components << endl;
  return 0;
}

def count_connected_components(matrix):
    rows, cols = len(matrix), len(matrix[0])
    visited = [[False]*cols for _ in range(rows)]

    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols or visited[r][c] or matrix[r][c] == 0:
            return
        visited[r][c] = True
        for dr, dc in [(0,1), (1,0), (0,-1), (-1,0)]:
            dfs(r+dr, c+dc)

    components = 0
    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == 1 and not visited[i][j]:
                components += 1
                dfs(i, j)

    return components

print(count_connected_components([
    [1,1,0,0],
    [0,1,0,0],
    [1,0,0,1],
    [0,0,1,1]
]))

public class ConnectedComponents {
    public static void main(String[] args) {
        int[][] matrix = {
            {1, 1, 0, 0},
            {0, 1, 0, 0},
            {1, 0, 0, 1},
            {0, 0, 1, 1}
        };
        System.out.println(countComponents(matrix));
    }

    public static int countComponents(int[][] matrix) {
        int rows = matrix.length, cols = matrix[0].length, components = 0;
        boolean[][] visited = new boolean[rows][cols];
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == 1 && !visited[i][j]) {
                    components++;
                    dfs(matrix, visited, i, j);
                }
            }
        }
        return components;
    }

    private static void dfs(int[][] matrix, boolean[][] visited, int r, int c) {
        int rows = matrix.length, cols = matrix[0].length;
        if (r < 0 || c < 0 || r >= rows || c >= cols || visited[r][c] || matrix[r][c] == 0) return;
        visited[r][c] = true;
        int[][] directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        for (int[] dir : directions) {
            dfs(matrix, visited, r + dir[0], c + dir[1]);
        }
    }
}

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

  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]
]));

package main

import (
  "fmt"
)

func dfs(matrix [][]int, visited [][]bool, r, c int) {
  rows, cols := len(matrix), len(matrix[0])
  if r < 0 || c < 0 || r >= rows || c >= cols || visited[r][c] || matrix[r][c] == 0 {
    return
  }
  visited[r][c] = true
  dirs := [][2]int{{0,1}, {1,0}, {0,-1}, {-1,0}}
  for _, d := range dirs {
    dfs(matrix, visited, r+d[0], c+d[1])
  }
}

func countComponents(matrix [][]int) int {
  rows, cols := len(matrix), len(matrix[0])
  visited := make([][]bool, rows)
  for i := range visited {
    visited[i] = make([]bool, cols)
  }
  components := 0
  for i := 0; i < rows; i++ {
    for j := 0; j < cols; j++ {
      if matrix[i][j] == 1 && !visited[i][j] {
        components++
        dfs(matrix, visited, i, j)
      }
    }
  }
  return components
}

func main() {
  matrix := [][]int{
    {1, 1, 0, 0},
    {0, 1, 0, 0},
    {1, 0, 0, 1},
    {0, 0, 1, 1},
  }
  fmt.Println(countComponents(matrix))
}

fn dfs(matrix: &Vec<Vec<i32>>, visited: &mut Vec<Vec<bool>>, r: i32, c: i32) {
    let rows = matrix.len() as i32;
    let cols = matrix[0].len() as i32;
    if r < 0 || c < 0 || r >= rows || c >= cols {
        return;
    }
    let (r_u, c_u) = (r as usize, c as usize);
    if visited[r_u][c_u] || matrix[r_u][c_u] == 0 {
        return;
    }
    visited[r_u][c_u] = true;
    for (dr, dc) in [(0,1), (1,0), (0,-1), (-1,0)] {
        dfs(matrix, visited, r + dr, c + dc);
    }
}

fn count_components(matrix: Vec<Vec<i32>>) -> i32 {
    let rows = matrix.len();
    let cols = matrix[0].len();
    let mut visited = vec![vec![false; cols]; rows];
    let mut count = 0;
    for i in 0..rows {
        for j in 0..cols {
            if matrix[i][j] == 1 && !visited[i][j] {
                count += 1;
                dfs(&matrix, &mut visited, i as i32, j as i32);
            }
        }
    }
    count
}

fn main() {
    let matrix = vec![
        vec![1, 1, 0, 0],
        vec![0, 1, 0, 0],
        vec![1, 0, 0, 1],
        vec![0, 0, 1, 1],
    ];
    println!("{}", count_components(matrix));
}

fun main() {
    val matrix = arrayOf(
        intArrayOf(1, 1, 0, 0),
        intArrayOf(0, 1, 0, 0),
        intArrayOf(1, 0, 0, 1),
        intArrayOf(0, 0, 1, 1)
    )
    println(countComponents(matrix))
}

fun countComponents(matrix: Array<IntArray>): Int {
    val rows = matrix.size
    val cols = matrix[0].size
    val visited = Array(rows) { BooleanArray(cols) }
    var count = 0

    fun dfs(r: Int, c: Int) {
        if (r !in 0 until rows || c !in 0 until cols || visited[r][c] || matrix[r][c] == 0) return
        visited[r][c] = true
        val dirs = arrayOf(Pair(0,1), Pair(1,0), Pair(0,-1), Pair(-1,0))
        for ((dr, dc) in dirs) dfs(r + dr, c + dc)
    }

    for (i in 0 until rows) {
        for (j in 0 until cols) {
            if (matrix[i][j] == 1 && !visited[i][j]) {
                count++
                dfs(i, j)
            }
        }
    }
    return count
}

func countComponents(_ matrix: [[Int]]) -> Int {
    let rows = matrix.count
    let cols = matrix[0].count
    var visited = Array(repeating: Array(repeating: false, count: cols), count: rows)
    var count = 0

    func dfs(_ r: Int, _ c: Int) {
        if r < 0 || c < 0 || r >= rows || c >= cols || visited[r][c] || matrix[r][c] == 0 {
            return
        }
        visited[r][c] = true
        let dirs = [(0,1), (1,0), (0,-1), (-1,0)]
        for (dr, dc) in dirs {
            dfs(r + dr, c + dc)
        }
    }

    for i in 0..<rows {
        for j in 0..<cols {
            if matrix[i][j] == 1 && !visited[i][j] {
                count += 1
                dfs(i, j)
            }
        }
    }
    return count
}

let matrix = [
  [1, 1, 0, 0],
  [0, 1, 0, 0],
  [1, 0, 0, 1],
  [0, 0, 1, 1]
]
print(countComponents(matrix))

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

  const directions = [
    [0, 1], [1, 0], [0, -1], [-1, 0]
  ];

  function dfs(r: number, c: number): void {
    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]
]));

Time complexity

Space complexity

O(m * n)

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