Skip to content

Find neighbours in 2D grid

Posted on:June 6, 2022 at 04:06 AM

Finding Neighbors in 2D Grids: A Complete Guide

Introduction to 2D Grids

A 2D grid is a fundamental data structure in computer science that represents a two-dimensional array of cells. Think of it like a chessboard, spreadsheet, or pixel matrix in an image. Each cell in the grid can be identified by its row and column coordinates, typically denoted as (i, j) where i is the row index and j is the column index.

The concept of “neighbors” refers to cells that are adjacent to a given cell. Depending on the problem, we may consider either 4 neighbors (cardinal directions) or 8 neighbors (cardinal + diagonal directions).

Finding 4 Neighbors in 2D Grid

The 4 neighbors (also called cardinal neighbors) of a cell are the cells directly above, below, left, and right of it. These represent movement in the four cardinal directions: North, South, East, and West.

Visual Representation

        [i-1][j]

[i][j-1] ← [i][j] → [i][j+1]

        [i+1][j]

Direction Vectors

We can use direction arrays to systematically explore all 4 neighbors:

Row offsets:    [-1,  0,  1,  0]
Column offsets: [ 0,  1,  0, -1]

These pairs represent: Up, Right, Down, Left respectively.

JavaScript Code

function find4Neighbors(grid, row, col) {
    const m = grid.length;        // number of rows
    const n = grid[0].length;     // number of columns
    const neighbors = [];

    // Direction vectors for 4 neighbors
    const dRow = [-1, 0, 1, 0];
    const dCol = [0, 1, 0, -1];

    // Check all 4 directions
    for (let i = 0; i < 4; i++) {
        const newRow = row + dRow[i];
        const newCol = col + dCol[i];

        // Check if the neighbor is within bounds
        if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
            neighbors.push(grid[newRow][newCol]);
        }
    }

    return neighbors;
}

Example

For a 5×5 grid, if we want to find neighbors of cell (2, 2):

Grid indices:
[0,0] [0,1] [0,2] [0,3] [0,4]
[1,0] [1,1] [1,2] [1,3] [1,4]
[2,0] [2,1] [2,2] [2,3] [2,4]  ← Cell (2,2) is at the center
[3,0] [3,1] [3,2] [3,3] [3,4]
[4,0] [4,1] [4,2] [4,3] [4,4]

The 4 neighbors are: (1,2), (2,3), (3,2), (2,1)


Finding 8 Neighbors in 2D Grid

The 8 neighbors include all cells surrounding a given cell: the 4 cardinal neighbors plus the 4 diagonal neighbors. This is useful when diagonal movement is allowed.

Visual Representation

[i-1][j-1]  [i-1][j]  [i-1][j+1]
[i][j-1]    [i][j]    [i][j+1]
[i+1][j-1]  [i+1][j]  [i+1][j+1]

Direction Vectors

Row offsets:    [-1, -1, -1,  0,  0,  1,  1,  1]
Column offsets: [-1,  0,  1, -1,  1, -1,  0,  1]

These represent all 8 directions around a cell.

JavaScript Code

function find8Neighbors(grid, row, col) {
    const m = grid.length;        // number of rows
    const n = grid[0].length;     // number of columns
    const neighbors = [];

    // Direction vectors for 8 neighbors
    const dRow = [-1, -1, -1, 0, 0, 1, 1, 1];
    const dCol = [-1, 0, 1, -1, 1, -1, 0, 1];

    // Check all 8 directions
    for (let i = 0; i < 8; i++) {
        const newRow = row + dRow[i];
        const newCol = col + dCol[i];

        // Check if the neighbor is within bounds
        if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
            neighbors.push(grid[newRow][newCol]);
        }
    }

    return neighbors;
}

Alternative Approach Using Nested Loops

The nested loops approach is often more intuitive for beginners because it directly mirrors how we think about neighbors: “check all cells around the target cell.”

How It Works

All 8 neighbors of a cell at position (row, col) exist within a 3×3 box centered on that cell:

┌─────────────────────────────────────────┐
│ (row-1,col-1) │ (row-1,col) │ (row-1,col+1) │  ← Top row
├─────────────────────────────────────────┤
│ (row,col-1)   │ (row,col)   │ (row,col+1)   │  ← Middle row
├─────────────────────────────────────────┤
│ (row+1,col-1) │ (row+1,col) │ (row+1,col+1) │  ← Bottom row
└─────────────────────────────────────────┘

The outer loop iterates through 3 rows (row-1, row, row+1), and the inner loop iterates through 3 columns (col-1, col, col+1). Together, they check all 9 cells in the 3×3 box. We skip the center cell since we only want neighbors.

JavaScript Code

function find8NeighborsAlt(grid, row, col) {
    const m = grid.length;        // number of rows
    const n = grid[0].length;     // number of columns
    const neighbors = [];

    // Check all cells in 3×3 area around (row, col)
    for (let i = row - 1; i <= row + 1; i++) {
        for (let j = col - 1; j <= col + 1; j++) {
            // Skip the center cell itself
            if (i === row && j === col) {
                continue;
            }

            // Check bounds
            if (i >= 0 && i < m && j >= 0 && j < n) {
                neighbors.push(grid[i][j]);
            }
        }
    }

    return neighbors;
}

Detailed Example

Consider a 5×5 grid where we want neighbors of cell (2, 2):

Grid with values:
  0   1   2   3   4
┌───┬───┬───┬───┬───┐
│ A │ B │ C │ D │ E │  0
├───┼───┼───┼───┼───┤
│ F │ G │ H │ I │ J │  1
├───┼───┼───┼───┼───┤
│ K │ L │ M │ N │ O │  2  ← Cell M is at (2,2)
├───┼───┼───┼───┼───┤
│ P │ Q │ R │ S │ T │  3
├───┼───┼───┼───┼───┤
│ U │ V │ W │ X │ Y │  4
└───┴───┴───┴───┴───┘

Execution trace:

i=1, j=1: Check (1,1) → G ✓ Valid neighbor
i=1, j=2: Check (1,2) → H ✓ Valid neighbor
i=1, j=3: Check (1,3) → I ✓ Valid neighbor
i=2, j=1: Check (2,1) → L ✓ Valid neighbor
i=2, j=2: Check (2,2) → M ✗ SKIP (center cell)
i=2, j=3: Check (2,3) → N ✓ Valid neighbor
i=3, j=1: Check (3,1) → Q ✓ Valid neighbor
i=3, j=2: Check (3,2) → R ✓ Valid neighbor
i=3, j=3: Check (3,3) → S ✓ Valid neighbor

Result: [G, H, I, L, N, Q, R, S]  (8 neighbors)

Handling Edge Cases

For cells at corners or edges, the boundary check automatically filters out invalid positions.

Example: Cell at (0, 0) (top-left corner)

i=-1, j=-1: (-1,-1) ✗ Out of bounds
i=-1, j=0:  (-1,0)  ✗ Out of bounds
i=-1, j=1:  (-1,1)  ✗ Out of bounds
i=0, j=-1:  (0,-1)  ✗ Out of bounds
i=0, j=0:   (0,0)   ✗ SKIP (center cell)
i=0, j=1:   (0,1)   ✓ Valid
i=1, j=-1:  (1,-1)  ✗ Out of bounds
i=1, j=0:   (1,0)   ✓ Valid
i=1, j=1:   (1,1)   ✓ Valid

Result: 3 neighbors (corner cells have fewer neighbors)

Finding 4 Neighbors in 2D Grid Represented as 1D Array

Sometimes, for memory efficiency or specific algorithmic requirements, a 2D grid is stored as a 1D array. In this representation, a cell at position (i, j) in the 2D grid is stored at index i × n + j in the 1D array, where n is the number of columns.

Conversion Formula

2D to 1D: index = row × numColumns + col
1D to 2D: row = Math.floor(index / numColumns)
          col = index % numColumns

JavaScript Code

function find4Neighbors1D(grid1D, index, numRows, numCols) {
    const neighbors = [];

    // Convert 1D index to 2D coordinates
    const row = Math.floor(index / numCols);
    const col = index % numCols;

    // Direction vectors
    const dRow = [-1, 0, 1, 0];
    const dCol = [0, 1, 0, -1];

    for (let i = 0; i < 4; i++) {
        const newRow = row + dRow[i];
        const newCol = col + dCol[i];

        // Check bounds
        if (newRow >= 0 && newRow < numRows && newCol >= 0 && newCol < numCols) {
            // Convert back to 1D index
            const neighbor1DIndex = newRow * numCols + newCol;
            neighbors.push(grid1D[neighbor1DIndex]);
        }
    }

    return neighbors;
}

Example

Consider a 3×4 grid (3 rows, 4 columns) stored as a 1D array:

2D Grid:               1D Array:
[0,0] [0,1] [0,2] [0,3]   → [0] [1] [2] [3]
[1,0] [1,1] [1,2] [1,3]   → [4] [5] [6] [7]
[2,0] [2,1] [2,2] [2,3]   → [8] [9] [10] [11]

For cell at 1D index 5 (which is 2D position (1,1)):


Finding 8 Neighbors in 2D Grid Represented as 1D Array

The concept is similar to finding 4 neighbors, but we check all 8 directions instead.

JavaScript Code

function find8Neighbors1D(grid1D, index, numRows, numCols) {
    const neighbors = [];

    // Convert 1D index to 2D coordinates
    const row = Math.floor(index / numCols);
    const col = index % numCols;

    // Direction vectors for 8 neighbors
    const dRow = [-1, -1, -1, 0, 0, 1, 1, 1];
    const dCol = [-1, 0, 1, -1, 1, -1, 0, 1];

    for (let i = 0; i < 8; i++) {
        const newRow = row + dRow[i];
        const newCol = col + dCol[i];

        // Check bounds
        if (newRow >= 0 && newRow < numRows && newCol >= 0 && newCol < numCols) {
            // Convert back to 1D index
            const neighbor1DIndex = newRow * numCols + newCol;
            neighbors.push(grid1D[neighbor1DIndex]);
        }
    }

    return neighbors;
}

Optimized Approach (Without Coordinate Conversion)

The Problem with Standard Approach

In the standard approach, for every neighbor we:

  1. Convert 1D index → 2D coordinates
  2. Add direction offsets
  3. Check bounds
  4. Convert 2D coordinates → 1D index

This involves many back-and-forth conversions. The optimized approach works directly with 1D indices.

Understanding 1D Offsets

Consider a 3×4 grid stored as a 1D array:

2D Grid:               1D Array indices:
[0,0] [0,1] [0,2] [0,3]   →   [0]  [1]  [2]  [3]
[1,0] [1,1] [1,2] [1,3]   →   [4]  [5]  [6]  [7]
[2,0] [2,1] [2,2] [2,3]   →   [8]  [9]  [10] [11]

If we’re at index 5 (position (1,1) in 2D), its 8 neighbors in the 1D array are:

         [1]  [2]  [3]
         [4]  [5]  [6]
         [8]  [9]  [10]

The differences between index 5 and its neighbors:

The pattern: For a grid with numCols columns, the offsets are:

Instead of converting coordinates, we can add these offsets directly to the current index!

JavaScript Code

function find8Neighbors1DOptimized(grid1D, index, numRows, numCols) {
    const neighbors = [];
    const row = Math.floor(index / numCols);
    const col = index % numCols;

    // Direct 1D index offsets
    const offsets = [
        -numCols - 1, -numCols, -numCols + 1,  // Top row
        -1, 1,                                   // Same row
        numCols - 1, numCols, numCols + 1       // Bottom row
    ];

    for (const offset of offsets) {
        const neighborIndex = index + offset;

        // Calculate what row and column this neighbor would be in
        const neighborRow = Math.floor(neighborIndex / numCols);
        const neighborCol = neighborIndex % numCols;

        // Verify the neighbor is valid:
        // 1. Within array bounds
        // 2. Row difference is at most 1
        // 3. Column difference is at most 1
        if (neighborIndex >= 0 && neighborIndex < (numRows * numCols)) {
            if (Math.abs(neighborRow - row) <= 1 && Math.abs(neighborCol - col) <= 1) {
                neighbors.push(grid1D[neighborIndex]);
            }
        }
    }

    return neighbors;
}

The Row Wrapping Problem

Simply adding offsets isn’t always safe. Consider index 3 in a 4-column grid:

Grid (4 columns):
[0]  [1]  [2]  [3]  ← We're at index 3 (position 0,3)
[4]  [5]  [6]  [7]
[8]  [9]  [10] [11]

If we add offset +1:

The offset wrapped around to the next row, giving an invalid neighbor.

Solution: We must verify that the neighbor is actually adjacent by checking:

  1. Basic bounds: Is the index in the array?
  2. Row distance: Is it at most 1 row away? (|neighborRow - row| ≤ 1)
  3. Column distance: Is it at most 1 column away? (|neighborCol - col| ≤ 1)

Complete Example Walkthrough

For index 3 in a 3×4 grid (position (0,3) - top-right):

OffsetneighborIndexneighborRowneighborColRow DiffCol DiffValid?
-5-2----❌ Out of bounds
-4-1----❌ Out of bounds
-300003❌ Col diff > 1
-120201✅ Valid
+141013❌ Col diff > 1
+361211✅ Valid
+471310✅ Valid
+582023❌ Row diff > 1

Valid neighbors: indices 2, 6, 7 (only 3 neighbors for a corner cell)