Introduction

Finding contiguous areas of 1 bits in a two-dimensional bit array is the standard connected-components problem on a grid. It appears in image processing, tile maps, bitmap compression, and any situation where you need to group adjacent occupied cells into meaningful regions.

Define Connectivity First

Before you write code, decide what “contiguous” means.

The two common choices are:

• 4-connectivity: up, down, left, right
• 8-connectivity: up, down, left, right, and diagonals

The choice changes the result. Two diagonal 1 cells are separate components with 4-connectivity but belong to the same component with 8-connectivity.

For example, in this grid:

1 0
0 1

there are two regions under 4-connectivity and one region under 8-connectivity.

The Standard Approach: Flood Fill

The usual solution is flood fill using DFS or BFS.

The algorithm is:

• scan every cell in the matrix
• when you find an unvisited 1, start a search from it
• mark every reachable 1 with the same component ID
• continue scanning for the next unvisited 1

This visits each cell at most once, so the runtime is linear in the grid size.

A Runnable BFS Example in Python

The example below finds all 4-connected regions and returns their coordinates.

1from collections import deque
2
3def connected_components(grid):
4    rows = len(grid)
5    cols = len(grid[0]) if rows else 0
6    visited = [[False] * cols for _ in range(rows)]
7    components = []
8    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
9
10    for r in range(rows):
11        for c in range(cols):
12            if grid[r][c] != 1 or visited[r][c]:
13                continue
14
15            queue = deque([(r, c)])
16            visited[r][c] = True
17            component = []
18
19            while queue:
20                cr, cc = queue.popleft()
21                component.append((cr, cc))
22
23                for dr, dc in directions:
24                    nr, nc = cr + dr, cc + dc
25                    if 0 <= nr < rows and 0 <= nc < cols:
26                        if grid[nr][nc] == 1 and not visited[nr][nc]:
27                            visited[nr][nc] = True
28                            queue.append((nr, nc))
29
30            components.append(component)
31
32    return components
33
34grid = [
35    [1, 0, 1, 1, 0],
36    [0, 1, 1, 0, 0],
37    [1, 1, 0, 1, 1],
38    [0, 0, 1, 0, 0],
39]
40
41for i, comp in enumerate(connected_components(grid), start=1):
42    print(f"component {i}: {comp}")

This example stores the coordinates for each region. If you only need the component count, you can increment a counter instead of storing the full list.

Labeling the Grid Instead of Returning Lists

Sometimes you want a labeled output image rather than coordinate lists. In that case, keep a second matrix of component IDs.

1def label_components(grid):
2    rows = len(grid)
3    cols = len(grid[0]) if rows else 0
4    labels = [[0] * cols for _ in range(rows)]
5    component_id = 0
6    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
7
8    def dfs(r, c, cid):
9        stack = [(r, c)]
10        labels[r][c] = cid
11        while stack:
12            cr, cc = stack.pop()
13            for dr, dc in directions:
14                nr, nc = cr + dr, cc + dc
15                if 0 <= nr < rows and 0 <= nc < cols:
16                    if grid[nr][nc] == 1 and labels[nr][nc] == 0:
17                        labels[nr][nc] = cid
18                        stack.append((nr, nc))
19
20    for r in range(rows):
21        for c in range(cols):
22            if grid[r][c] == 1 and labels[r][c] == 0:
23                component_id += 1
24                dfs(r, c, component_id)
25
26    return labels

This is useful for later processing such as measuring component size, bounding boxes, or perimeter.

Complexity and Tradeoffs

For a grid with R * C cells:

• time complexity is O(R * C)
• extra space is O(R * C) in the worst case for visited state and queue or stack

DFS and BFS are both fine. BFS is iterative and avoids recursion depth issues in large regions. Recursive DFS can be elegant, but very large grids can overflow the call stack.

For streaming or incremental updates, Union-Find can also work well, but for one-pass analysis of a static grid, BFS or DFS is usually simpler.

Common Pitfalls

The biggest mistake is failing to define connectivity explicitly. A correct 4-connected implementation can still look wrong if the expected answer assumed 8-connectivity.

Another mistake is forgetting boundary checks, which leads to index errors at the grid edges.

A third issue is not marking cells as visited soon enough. If you wait too long, the same cell may be enqueued or pushed multiple times.

Finally, recursive DFS is risky on very large components because the language call stack, not the algorithm itself, becomes the limiting factor.

Summary

• Finding contiguous bit areas is a connected-components problem on a grid.
• Decide between 4-connectivity and 8-connectivity before implementing anything.
• BFS and DFS both solve the problem in linear time.
• Use labeling when you need a component map, not just a component count.
• Mark cells as visited as soon as they are discovered.
• For large inputs, prefer iterative traversal over recursive DFS.