Get adjacent elements in a two-dimensional array?

Efficiently Finding Adjacent Elements in a 2D Array

Learn various algorithms and programming techniques to identify and retrieve adjacent elements (neighbors) for any given cell in a two-dimensional array or matrix, considering edge cases and boundaries.

Working with two-dimensional arrays, often referred to as matrices or grids, is a common task in programming. A frequent requirement is to find the "adjacent" elements to a specific cell. Adjacency can be defined in a few ways: directly above, below, left, and right (4-directional or Von Neumann neighborhood), or including diagonals (8-directional or Moore neighborhood). Understanding how to correctly identify these neighbors, especially when dealing with array boundaries, is crucial for many algorithms, including pathfinding, game development (e.g., Conway's Game of Life), image processing, and more.

Defining Adjacency: 4-Directional vs. 8-Directional

Before implementing any logic, it's important to clarify what constitutes an "adjacent" element. The two most common definitions are:

1. 4-Directional Adjacency (Von Neumann Neighborhood): This includes cells that share a common edge with the target cell. These are the cells directly above, below, to the left, and to the right.
2. 8-Directional Adjacency (Moore Neighborhood): This includes all cells that share either an edge or a corner with the target cell. This expands the 4-directional neighbors to also include the four diagonal cells.

graph TD
    subgraph "Target Cell (R, C)"
        T(Target Cell) -- Row R, Col C --> T
    end

    subgraph "4-Directional Neighbors"
        N4_U(R-1, C) -- Up --> T
        N4_D(R+1, C) -- Down --> T
        N4_L(R, C-1) -- Left --> T
        N4_R(R, C+1) -- Right --> T
    end

    subgraph "8-Directional Neighbors (includes 4-directional)"
        N8_UL(R-1, C-1) -- Up-Left --> T
        N8_UR(R-1, C+1) -- Up-Right --> T
        N8_DL(R+1, C-1) -- Down-Left --> T
        N8_DR(R+1, C+1) -- Down-Right --> T
    end

    N4_U --> N8_UL
    N4_U --> N8_UR
    N4_D --> N8_DL
    N4_D --> N8_DR
    N4_L --> N8_UL
    N4_L --> N8_DL
    N4_R --> N8_UR
    N4_R --> N8_DR

    style T fill:#f9f,stroke:#333,stroke-width:2px
    style N4_U fill:#ccf,stroke:#333,stroke-width:1px
    style N4_D fill:#ccf,stroke:#333,stroke-width:1px
    style N4_L fill:#ccf,stroke:#333,stroke-width:1px
    style N4_R fill:#ccf,stroke:#333,stroke-width:1px
    style N8_UL fill:#cfc,stroke:#333,stroke-width:1px
    style N8_UR fill:#cfc,stroke:#333,stroke-width:1px
    style N8_DL fill:#cfc,stroke:#333,stroke-width:1px
    style N8_DR fill:#cfc,stroke:#333,stroke-width:1px

Visualizing 4-directional (blue) and 8-directional (green) neighbors around a target cell.

Algorithm for Finding Neighbors

The core idea is to iterate through a predefined set of relative offsets (changes in row and column indices) from the target cell's coordinates. For each offset, calculate the potential neighbor's coordinates and then validate if these coordinates are within the bounds of the array. This approach is highly flexible and language-agnostic.

Implementation Details and Boundary Checks

When calculating neighbor coordinates, it's crucial to perform boundary checks. A neighbor is only valid if its row and column indices fall within the array's dimensions. If the array has rows rows and cols columns, then for a potential neighbor at (new_row, new_col):

• 0 <= new_row < rows
• 0 <= new_col < cols

Let's look at a common implementation pattern.

Python

def get_adjacent_elements(matrix, r, c, include_diagonals=False): rows = len(matrix) cols = len(matrix[0]) neighbors = []

# 4-directional offsets
dr = [-1, 1, 0, 0]  # Up, Down, Left, Right
dc = [0, 0, -1, 1]

if include_diagonals:
    # Add diagonal offsets for 8-directional
    dr.extend([-1, -1, 1, 1])
    dc.extend([-1, 1, -1, 1])

for i in range(len(dr)):
    nr, nc = r + dr[i], c + dc[i]

    # Boundary check
    if 0 <= nr < rows and 0 <= nc < cols:
        neighbors.append(matrix[nr][nc])
        
return neighbors

Example Usage:

matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]

print(f"Neighbors of (1,1) (value 5) (4-directional): {get_adjacent_elements(matrix, 1, 1)}")

Expected: [2, 8, 4, 6]

print(f"Neighbors of (0,0) (value 1) (8-directional): {get_adjacent_elements(matrix, 0, 0, True)}")

Expected: [4, 2, 5]

print(f"Neighbors of (1,1) (value 5) (8-directional): {get_adjacent_elements(matrix, 1, 1, True)}")

Expected: [2, 8, 4, 6, 1, 3, 7, 9]

JavaScript

function getAdjacentElements(matrix, r, c, includeDiagonals = false) { const rows = matrix.length; const cols = matrix[0].length; const neighbors = [];

// 4-directional offsets
let dr = [-1, 1, 0, 0]; // Up, Down, Left, Right
let dc = [0, 0, -1, 1];

if (includeDiagonals) {
    // Add diagonal offsets for 8-directional
    dr = dr.concat([-1, -1, 1, 1]);
    dc = dc.concat([-1, 1, -1, 1]);
}

for (let i = 0; i < dr.length; i++) {
    const nr = r + dr[i];
    const nc = c + dc[i];

    // Boundary check
    if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
        neighbors.push(matrix[nr][nc]);
    }
}
return neighbors;

}

// Example Usage: const matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ];

console.log(Neighbors of (1,1) (value 5) (4-directional): ${getAdjacentElements(matrix, 1, 1)}); // Expected: [2, 8, 4, 6]

console.log(Neighbors of (0,0) (value 1) (8-directional): ${getAdjacentElements(matrix, 0, 0, true)}); // Expected: [4, 2, 5]

console.log(Neighbors of (1,1) (value 5) (8-directional): ${getAdjacentElements(matrix, 1, 1, true)}); // Expected: [2, 8, 4, 6, 1, 3, 7, 9]

Java

import java.util.ArrayList; import java.util.List;

public class MatrixNeighbors {

public static List<Integer> getAdjacentElements(int[][] matrix, int r, int c, boolean includeDiagonals) {
    int rows = matrix.length;
    int cols = matrix[0].length;
    List<Integer> neighbors = new ArrayList<>();

    // 4-directional offsets
    int[] dr4 = {-1, 1, 0, 0}; // Up, Down, Left, Right
    int[] dc4 = {0, 0, -1, 1};

    // 8-directional offsets (includes 4-directional)
    int[] dr8 = {-1, -1, -1, 0, 0, 1, 1, 1};
    int[] dc8 = {-1, 0, 1, -1, 1, -1, 0, 1};

    int[] currentDr = includeDiagonals ? dr8 : dr4;
    int[] currentDc = includeDiagonals ? dc8 : dc4;

    for (int i = 0; i < currentDr.length; i++) {
        int nr = r + currentDr[i];
        int nc = c + currentDc[i];

        // Boundary check
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
            neighbors.add(matrix[nr][nc]);
        }
    }
    return neighbors;
}

public static void main(String[] args) {
    int[][] matrix = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };

    System.out.println("Neighbors of (1,1) (value 5) (4-directional): " + getAdjacentElements(matrix, 1, 1, false));
    // Expected: [2, 8, 4, 6]

    System.out.println("Neighbors of (0,0) (value 1) (8-directional): " + getAdjacentElements(matrix, 0, 0, true));
    // Expected: [4, 2, 5]

    System.out.println("Neighbors of (1,1) (value 5) (8-directional): " + getAdjacentElements(matrix, 1, 1, true));
    // Expected: [2, 8, 4, 6, 1, 3, 7, 9]
}

}

Handling Edge Cases and Irregular Arrays

The provided algorithms assume a rectangular (or square) 2D array where all rows have the same number of columns. If you are dealing with a 'jagged' array (where rows can have different lengths), the cols variable should be determined for each row individually (e.g., matrix[nr].length in Java/JavaScript, or len(matrix[nr]) in Python) during the boundary check for nc.

By using this flexible offset-based approach with robust boundary checks, you can reliably find adjacent elements in any 2D array, adapting easily to different definitions of adjacency and array structures.