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)
):
- Row = Math.floor(5 / 4) = 1
- Col = 5 % 4 = 1
- Neighbors in 2D:
(0,1)
,(1,2)
,(2,1)
,(1,0)
- Neighbors in 1D: indices 1, 6, 9, 4
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:
- Convert 1D index → 2D coordinates
- Add direction offsets
- Check bounds
- 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:
1 - 5 = -4
(top-left)2 - 5 = -3
(top)3 - 5 = -2
(top-right)4 - 5 = -1
(left)6 - 5 = +1
(right)8 - 5 = +3
(bottom-left)9 - 5 = +4
(bottom)10 - 5 = +5
(bottom-right)
The pattern: For a grid with numCols
columns, the offsets are:
- Top row:
-numCols-1
,-numCols
,-numCols+1
- Same row:
-1
,+1
- Bottom row:
+numCols-1
,+numCols
,+numCols+1
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
:
3 + 1 = 4
- But index 4 is position
(1,0)
- wrong row!
The offset wrapped around to the next row, giving an invalid neighbor.
Solution: We must verify that the neighbor is actually adjacent by checking:
- Basic bounds: Is the index in the array?
- Row distance: Is it at most 1 row away? (
|neighborRow - row| ≤ 1
) - 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):
Offset | neighborIndex | neighborRow | neighborCol | Row Diff | Col Diff | Valid? |
---|---|---|---|---|---|---|
-5 | -2 | - | - | - | - | ❌ Out of bounds |
-4 | -1 | - | - | - | - | ❌ Out of bounds |
-3 | 0 | 0 | 0 | 0 | 3 | ❌ Col diff > 1 |
-1 | 2 | 0 | 2 | 0 | 1 | ✅ Valid |
+1 | 4 | 1 | 0 | 1 | 3 | ❌ Col diff > 1 |
+3 | 6 | 1 | 2 | 1 | 1 | ✅ Valid |
+4 | 7 | 1 | 3 | 1 | 0 | ✅ Valid |
+5 | 8 | 2 | 0 | 2 | 3 | ❌ Row diff > 1 |
Valid neighbors: indices 2, 6, 7 (only 3 neighbors for a corner cell)