Go back

Find neighbours in 2D grid

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)

Share this post on:
Share this post via WhatsAppShare this post on FacebookShare this post on XShare this post via TelegramShare this post on PinterestShare this post via email
Previous Post
Identifying cycle in directed graph
Next Post
Representing 2D array as 1D array