Finding Neighbors of a Matrix Cell | Baeldung on Computer Science

1. Introduction

In this tutorial, we’ll show how to find neighbors of a cell in a two-dimensional matrix.

2. Neighbors

Let’s say we have an $m \times n$ matrix $A$ . We want to get all the neighbors of $\boldsymbol{A[i, j]}$ , the cell in the $\boldsymbol{i}$ -th row and $\boldsymbol{j}$ -th column ( $1 \leq i \leq m, 1 \leq j \leq n$ ).

Usually, we define a cell’s neighbors as all the cells it borders with horizontally, vertically, or diagonally:

The vertical neighbors of $A[i, j]$ are $A[i - 1, j]$ and $A[i + 1, j]$ . They’re in the same column as $A[i, j]$ , right above and below it. Similarly, its horizontal neighbors are $A[i, j - 1]$ and $A[i, j + 1]$ : the cells right to its left and right.

The diagonal neighbors are in the corners of the neighborhood square. The top left is $A[i - 1, j - 1]$ , the top right $A[i - 1, j + 1]$ , the bottom left is $A[i + 1, j - 1]$ , and the bottom right $A[i + 1, j + 1]$ .

3. Iterating Over Neighbors

From the above, it follows that we can iterate over all the combinations of $\boldsymbol{i-1, i, i+1}$ and $\boldsymbol{j-1, j, j+1}$ to get the neighbors of $\boldsymbol{A[i, j]}$ . In doing so, we need to take care of two things.

First, it makes no sense to return $\boldsymbol{A[i, j]}$ as its own neighbor, so we’ll omit the combination $(i,j)$ . Additionally, if $\boldsymbol{A[i, j]}$ is at a border, some combinations will be illegal since they’ll be outside the matrix, so we need to skip them. For example, if $j=n$ , there are no neighbors to the right of $A[i, n]$ :

Taking those two points into account, we get the neighbors of $A[i, j]$ as follows:

A problem with this approach is that the neighborhood is hard-coded. So, if we want to define neighbors differently, we need to change the loops. Depending on the neighborhood definition, that can be cumbersome and prone to errors.

4. Iterating Over Offsets

A more flexible approach is to iterate over offsets. For instance, the offset of $A[i-1, j+1]$ to $A[i, j]$ is $(-1, +1)$ . So, if we have the offsets, we can iterate over them to get the neighbors of $A[i, j]$ :

We can define a neighborhood in various ways:

Although more flexible, this approach requires us to generate the offsets first. One way to do so is to use the corresponding distance function. For example, the Manhattan distances in the standard neighborhood are either 1 or 2. So, the offsets are in the set:

$\left\{ (\Delta i, \Delta j) \in \{-1, 0, 1\}^2 \mid \Delta i + \Delta j \in \{1, 2\} \right\}$

We can also plug in the boundary checks so that all the offsets are safe:

$\left\{ (\Delta i, \Delta j) \in \{-1, 0, 1\}^2 \mid \Delta i + \Delta j \in \{1, 2\} \,\, \land \,\, 1 \leq i + \Delta i \leq m \,\, \land \,\, 1 \leq j + \Delta j \leq n \right\}$

In that case, we don’t need any checks in the above algorithm.

5. Conclusion

In this article, we showed how to find neighbors of a cell in a 2D matrix.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex

1. Introduction

2. Neighbors

3. Iterating Over Neighbors

4. Iterating Over Offsets

5. Conclusion