Introduction

Counting groups of equal cells in a 2D grid is a connected-components problem. The standard solution is to scan the grid and start a traversal such as depth-first search or breadth-first search whenever you find an unvisited cell, marking every connected cell of the same value as part of that group.

Define What Counts as a Group

Before writing code, decide the adjacency rule. Two common choices are:

• four-directional adjacency: up, down, left, right
• eight-directional adjacency: the four directions above plus diagonals

The group count can change depending on that definition, so the algorithm must encode the same rule the problem expects.

For example, in four-directional mode, diagonal neighbors do not belong to the same group unless there is a path through side-adjacent cells.

DFS Approach

A depth-first search is often the simplest implementation. When you find an unvisited cell, you start a DFS that visits all same-valued connected neighbors. That whole traversal counts as one group.

1def count_groups(grid):
2    if not grid or not grid[0]:
3        return 0
4
5    rows = len(grid)
6    cols = len(grid[0])
7    visited = [[False] * cols for _ in range(rows)]
8    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
9
10    def dfs(r, c, value):
11        visited[r][c] = True
12        for dr, dc in directions:
13            nr, nc = r + dr, c + dc
14            if 0 <= nr < rows and 0 <= nc < cols:
15                if not visited[nr][nc] and grid[nr][nc] == value:
16                    dfs(nr, nc, value)
17
18    groups = 0
19    for r in range(rows):
20        for c in range(cols):
21            if not visited[r][c]:
22                groups += 1
23                dfs(r, c, grid[r][c])
24
25    return groups
26
27
28grid = [
29    [1, 1, 2, 2],
30    [1, 2, 2, 3],
31    [4, 4, 3, 3],
32]
33
34print(count_groups(grid))

This counts connected regions by value under four-directional adjacency.

BFS Works Too

Breadth-first search solves the same problem with a queue instead of recursion. That can be useful if you want to avoid recursion-depth issues on large grids.

1from collections import deque
2
3
4def bfs(grid, start_r, start_c, visited):
5    rows, cols = len(grid), len(grid[0])
6    value = grid[start_r][start_c]
7    q = deque([(start_r, start_c)])
8    visited[start_r][start_c] = True
9    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
10
11    while q:
12        r, c = q.popleft()
13        for dr, dc in directions:
14            nr, nc = r + dr, c + dc
15            if 0 <= nr < rows and 0 <= nc < cols:
16                if not visited[nr][nc] and grid[nr][nc] == value:
17                    visited[nr][nc] = True
18                    q.append((nr, nc))

The overall counting loop stays the same. Only the traversal mechanism changes.

Complexity

Each cell is visited once, so the time complexity is O(rows * cols). The visited matrix also costs O(rows * cols) space, and DFS or BFS needs additional stack or queue space proportional to the size of a component.

That is already optimal for this style of full-grid traversal because every cell must be examined at least once.

Common Pitfalls

• Failing to define whether adjacency is four-directional or eight-directional changes the answer. Match the traversal rule to the problem statement exactly.
• Forgetting a visited structure causes repeated work or infinite recursion as the search revisits the same cells. Mark cells as soon as they are discovered.
• Counting every equal value instead of every connected region solves a different problem. Groups depend on connectivity, not only on value frequency.
• Using recursive DFS on a very large grid can hit recursion limits in Python. Switch to BFS or an explicit stack if the input may be large.
• Starting a new traversal before checking visited inflates the group count. Only launch DFS or BFS from cells that have not already been assigned to a group.

Summary

• Counting same-valued groups in a 2D array is a connected-components problem.
• Scan the grid and run DFS or BFS from each unvisited cell.
• Mark all connected cells with the same value during that traversal.
• The result depends on whether adjacency is four-directional or eight-directional.
• A correct solution visits each cell once, so the time complexity is linear in the number of cells.