Grid Traversal: 4 and 8 Neighbours in a 2D Matrix

Every grid problem, from flood fill to shortest paths to Game of Life, rests on one small piece of code: given a cell, list its neighbours. It is four lines long and it is where most grid bugs live: row and column swapped, a missing bounds check, a negative index that Python happily accepts. This article covers the neighbour loop itself, for 4 and 8 directions, the guard that keeps it honest, and the counts you can check it against.

The problem it solves

A grid is stored as a list of rows, so grid[r][c] is row r, column c. Moving around it means adding offsets to that pair, and every offset can land outside the grid at an edge or a corner.

Searches built on top of this primitive, such as flood fill, number of islands and multi-source BFS, each have their own article. They all call the same neighbour function, and if it is wrong, every one of them is wrong in the same way.

The intuition

Row first, always. r picks the row, which is the vertical position; c picks the column. Up is (r - 1, c), not (r, c - 1). If you think in x and y, then x is the column and y is the row, which is exactly backwards from the index order, and a common source of transposed answers.

Neighbours are a list of offsets. Four directions share an edge with the cell: (-1, 0), (1, 0), (0, -1), (0, 1). Eight directions add the diagonals: (-1, -1), (-1, 1), (1, -1), (1, 1). Looping over a list replaces four or eight hand-written branches, and switching between the two is a one-word change. Other move sets, a knight's eight jumps for example, are just another list.

Every candidate needs the guard 0 <= nr < rows and 0 <= nc < cols. Without it, Python does not raise for a negative index: grid[-1] is the last row. A missing check at the top edge does not crash; it quietly reads the bottom of the grid, and the bug looks like a wrong answer rather than an error. Only the bottom and right edges raise IndexError.

The guard also fixes how many neighbours a cell has: with 4 directions, 2 at a corner, 3 on an edge, 4 inside; with 8, it is 3, 5 and 8. A whole grid has rows × (cols - 1) + cols × (rows - 1) adjacent pairs, plus 2 × (rows - 1) × (cols - 1) diagonal ones. Those numbers make a precise test for any neighbour function.

Watch it run

A grid is a list of rows, so grid[r][c] is row r, column c: row first, every time. The 3 × 4 grid holds the numbers 0 to 11. Stand on r = 1, c = 1; the value under you is grid[1][1] = 5. Up is not c - 1. Up is (r - 1, c): the row index moves and the column stays put. Four neighbours, four offsets, and the lesson loops over them instead of writing four if-statements.

Move to the corner and the same four offsets behave very differently. Two of them walk off the board: row −1 and column −1 do not exist. Python would not even complain: index −1 quietly means the last row, and the bug wraps around the grid, landing on the 8 at the bottom-left. So every read is guarded by one line, 0 <= r < rows and 0 <= c < cols. Some problems count the diagonals as well: eight offsets instead of four, same guard. And a plain sweep touches all twelve cells once: O(rows × cols), whatever happens inside.

The code

One neighbour function that takes the offset list as a parameter, the counts by position, the wrap-around bug, and a full-grid sweep that uses 8-neighbours: the number on each cell of a minesweeper board.

import random

DIRS4 = [(-1, 0), (1, 0), (0, -1), (0, 1)]                  # up, down, left, right
DIRS8 = DIRS4 + [(-1, -1), (-1, 1), (1, -1), (1, 1)]         # plus the four diagonals

def neighbours(rows, cols, r, c, dirs=DIRS4):
    for dr, dc in dirs:
        nr, nc = r + dr, c + dc
        if 0 <= nr < rows and 0 <= nc < cols:                # the guard, every time
            yield nr, nc

for r, c in [(0, 0), (0, 1), (1, 1)]:                         # corner, edge, inside
    print((r, c), len(list(neighbours(3, 4, r, c))), len(list(neighbours(3, 4, r, c, DIRS8))))
# (0, 0) 2 3
# (0, 1) 3 5
# (1, 1) 4 8

grid = [[0, 1, 2, 3],
        [4, 5, 6, 7],
        [8, 9, 10, 11]]
r, c = 0, 0
print(grid[r - 1][c])          # 8  -> no IndexError: row -1 is the LAST row

def mine_counts(board):
    """Every cell: how many of its 8 neighbours hold a mine. One sweep, row by row."""
    rows, cols = len(board), len(board[0])
    return ["".join("*" if board[r][c] == "*" else
                    str(sum(board[nr][nc] == "*" for nr, nc in neighbours(rows, cols, r, c, DIRS8)))
                    for c in range(cols)) for r in range(rows)]

for line in mine_counts(["*...",
                         "..*.",
                         "...."]):
    print(line)
# *211
# 12*1
# 0111

cols = 4
cell = 1 * cols + 2                       # (1, 2) as one integer: handy for sets and union-find
print(cell, divmod(cell, cols))           # 6 (1, 2)

The last two lines flatten a cell to one integer, r × cols + c, and back with divmod. That is the usual way to put grid cells into a union-find parent array or a visited bitmap.

The seeded check: on 500 random grid shapes, including single rows and single columns, the offset-based neighbours of every cell must equal a brute force that tests every cell in the grid by distance (Manhattan distance 1 for four directions, Chebyshev distance 1 for eight). The pair counts must match the formulas, the flattening must round-trip, and the minesweeper numbers must match a count over the whole board:

rng = random.Random(39)
ok = True
for _ in range(500):
    rows, cols = rng.randint(1, 7), rng.randint(1, 7)
    cells = [(r, c) for r in range(rows) for c in range(cols)]
    pairs4 = pairs8 = 0
    for r, c in cells:
        # brute force: test every cell of the grid by distance instead of using offsets
        near4 = {(a, b) for a, b in cells if abs(a - r) + abs(b - c) == 1}
        near8 = {(a, b) for a, b in cells if max(abs(a - r), abs(b - c)) == 1}
        ok &= set(neighbours(rows, cols, r, c)) == near4
        ok &= set(neighbours(rows, cols, r, c, DIRS8)) == near8
        ok &= divmod(r * cols + c, cols) == (r, c)
        pairs4 += len(near4)
        pairs8 += len(near8)
    ok &= pairs4 // 2 == rows * (cols - 1) + cols * (rows - 1)      # edges, each seen twice
    ok &= pairs8 // 2 == pairs4 // 2 + 2 * (rows - 1) * (cols - 1)  # plus two diagonals per square
    board = ["".join(rng.choice("*..") for _ in range(cols)) for _ in range(rows)]
    for r, line in enumerate(mine_counts(board)):
        for c, ch in enumerate(line):
            mines = sum(board[a][b] == "*" for a, b in cells if max(abs(a - r), abs(b - c)) == 1)
            ok &= ch == ("*" if board[r][c] == "*" else str(mines))
print(ok)                                  # True

The complexity

• One neighbour query: O(d) for d directions, 4 or 8, so O(1).
• A full sweep: O(rows × cols) cells, times d if each cell inspects its neighbours: still O(rows × cols).

Where it goes wrong

• Swapping row and column. grid[x][y] with x as the horizontal position reads the transpose.
• Skipping the guard at the top or left. Negative indexes wrap silently; only the bottom and right edges raise.
• Using cols = len(grid[0]) on an empty grid. Check if not grid first.
• Mixing 4 and 8. "Connected" means 4-neighbours unless the problem says diagonals count; the answer changes.
• Updating in place during a sweep. Game of Life must read the old generation; write to a copy or encode both states.

When it shows up in interviews

Inside nearly every grid question: islands, rotting oranges, word search, shortest path in a binary matrix, Game of Life, minesweeper. Interviewers rarely ask for the neighbour loop alone, but they notice immediately when it is four copy-pasted if blocks with one bound wrong. The patterns cheat sheet groups the grid searches that build on it.

How to say it in an interview

"I index row first, grid[r][c], and keep the moves as a list of offsets: four for edge-sharing neighbours, eight if diagonals count. For each candidate I check 0 <= nr < rows and 0 <= nc < cols before reading, because in Python a negative index wraps to the other side instead of raising. A full pass is O(rows × cols), and the neighbour loop adds only a constant factor."