Introduction

In a binary matrix, a "hole" usually means a region of empty cells that is completely enclosed by filled cells. The standard way to find holes is not to search for enclosed regions directly, but to mark every empty cell that can reach the boundary. Any empty cell left unmarked afterward belongs to a hole.

Define the Connectivity Rule First

Before writing code, decide what counts as connected:

• four-directional connectivity using up, down, left, and right
• eight-directional connectivity including diagonals

Most grid problems default to four-directional connectivity unless the problem statement says otherwise. The answer can change depending on that rule.

The Key Insight

A hole cannot touch the outer border of the matrix. So instead of starting from interior cells, start from all boundary zero cells and flood-fill outward through connected zero cells. Those cells are not holes because they can escape to the boundary.

After that flood fill:

• visited zero cells are outside or boundary-connected space
• unvisited zero cells are enclosed holes

This gives a linear-time algorithm.

Breadth-First Search Solution

Here is a Python implementation using breadth-first search.

1from collections import deque
2
3def find_hole_cells(grid):
4    rows, cols = len(grid), len(grid[0])
5    seen = [[False] * cols for _ in range(rows)]
6    q = deque()
7
8    def add(r, c):
9        if 0 <= r < rows and 0 <= c < cols and not seen[r][c] and grid[r][c] == 0:
10            seen[r][c] = True
11            q.append((r, c))
12
13    for r in range(rows):
14        add(r, 0)
15        add(r, cols - 1)
16
17    for c in range(cols):
18        add(0, c)
19        add(rows - 1, c)
20
21    while q:
22        r, c = q.popleft()
23        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
24            add(r + dr, c + dc)
25
26    holes = []
27    for r in range(rows):
28        for c in range(cols):
29            if grid[r][c] == 0 and not seen[r][c]:
30                holes.append((r, c))
31
32    return holes
33
34grid = [
35    [1, 1, 1, 1, 1],
36    [1, 0, 0, 1, 1],
37    [1, 0, 1, 0, 1],
38    [1, 1, 1, 1, 1],
39]
40
41print(find_hole_cells(grid))

This returns the coordinates of all zero cells that belong to holes.

Finding Separate Hole Regions

Sometimes you do not just want the cells. You want each hole as its own connected component. In that case, do a second flood fill over the remaining unvisited zero cells.

1from collections import deque
2
3def find_hole_regions(grid):
4    rows, cols = len(grid), len(grid[0])
5    outside = [[False] * cols for _ in range(rows)]
6
7    def neighbors(r, c):
8        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
9            nr, nc = r + dr, c + dc
10            if 0 <= nr < rows and 0 <= nc < cols:
11                yield nr, nc
12
13    q = deque()
14    for r in range(rows):
15        for c in (0, cols - 1):
16            if grid[r][c] == 0 and not outside[r][c]:
17                outside[r][c] = True
18                q.append((r, c))
19
20    for c in range(cols):
21        for r in (0, rows - 1):
22            if grid[r][c] == 0 and not outside[r][c]:
23                outside[r][c] = True
24                q.append((r, c))
25
26    while q:
27        r, c = q.popleft()
28        for nr, nc in neighbors(r, c):
29            if grid[nr][nc] == 0 and not outside[nr][nc]:
30                outside[nr][nc] = True
31                q.append((nr, nc))
32
33    regions = []
34    seen = [[False] * cols for _ in range(rows)]
35
36    for r in range(rows):
37        for c in range(cols):
38            if grid[r][c] == 0 and not outside[r][c] and not seen[r][c]:
39                region = []
40                q = deque([(r, c)])
41                seen[r][c] = True
42                while q:
43                    cr, cc = q.popleft()
44                    region.append((cr, cc))
45                    for nr, nc in neighbors(cr, cc):
46                        if grid[nr][nc] == 0 and not outside[nr][nc] and not seen[nr][nc]:
47                            seen[nr][nc] = True
48                            q.append((nr, nc))
49                regions.append(region)
50
51    return regions

This groups enclosed zero cells into separate holes.

Complexity

The algorithm visits each cell at most a constant number of times, so the time complexity is O(rows * cols). The extra memory is also O(rows * cols) if you store visited state separately.

That is about as good as it gets for a general matrix scan because you must at least inspect the grid.

Common Pitfalls

The biggest pitfall is trying to decide whether each zero is a hole using only local neighbors. Hole detection is global. A zero may look enclosed nearby but still connect to the boundary through a longer path.

Another issue is forgetting to define connectivity. Four-directional and eight-directional rules can produce different answers.

Developers also mutate the original matrix too early and then lose track of which cells were originally empty. That is fine if done intentionally, but use a separate visited structure when clarity matters more than in-place optimization.

Finally, watch out for edge cases such as empty grids, one-row grids, or one-column grids where no interior hole can exist under the usual definition.

Summary

• A hole is an empty region that cannot reach the boundary.
• Flood-fill from boundary empty cells first, then treat the remaining empty cells as holes.
• Use BFS or DFS; both work with the same idea.
• Decide whether connectivity is four-directional or eight-directional before coding.
• The standard approach runs in linear time over the size of the matrix.