Traversing a 2D Matrix

(Updated ) 5 min read · , , ,

The new years first blog is about algorithms – more precisely: 2 dimensional matrices. I want to explore the ways how to find connected 1’s (so called islands) in a 2D array. This problem is also known as the “find the number of islands” or “connected components in an undirected graph“. In this post, we will explore traversing a 2D matrix.

Disclaimer: I generally use my own Algorithms & Data Structures library PHPAlgorithms for examples. If not otherwise declared, the following examples base also on this library.

The subject about this issue is to think in a graph context (even if we talk about 2D arrays). Doing this, we can easily determine that the problem is about a Depth-First-Search (DFS). But lets start with a simple example:

traversing matrix: The connected red 1's represent an "island" and the green 0's are the "water"
islands in a 2D array.

The example shows a 4 x 4 2D matrix with 2 islands denoted by (red) 1’s. The cells with a 0 are non-islands (so called “water”). Before I start, here are some basic definitions:

  • Neighbor: any two cells that have both the same value and share a N/S/E/W edge
  • Island: The collection of multiple neighbors

The matrix traversing Algorithm

Starting at cell [0/0], the algorithm iterates first over the rows and then the columns. If the current cell is a 1, the algorithm floods through all neighbors (and repeats it for all neighbor’s neighbors) until it reachs the water. At this point, we have to remember that we need a way to remember which cells are already visited in order to prevent multiple visiting (as we are traversing in DFS).
We can use a second “visited” array which contains all visited cells. But personally, I think there’s a much more elegant way: just switching all visited 1’s to 0’s. This makes a second array redundant and the code gets much more elegant. If you consider this approach, do not forget to pass the array by reference as the switching 1’s to 0 will get useless since the most programming language pass variables by value.

This algorithm is repeated for all cells in the array. Whenever a cell with a 1 is found, a counter is incremented (that represents the amount of the islands). The algorithm has a O(n*m) runtime and O(n*m) space complexity.

The matrix traversing Code

Enough theory, let’s start with the code. I am going through each function:


function countIslands(array $matrix) {
    $islandCount = 0;
    $iSize = count($matrix);
    for ($i = 0; $i < $iSize; $i++) {
        $jSize = count($matrix[$i]);
        for ($j = 0; $j < $jSize; $j++) {
            if (isIslandCell($matrix[$i][$j])) {
                $islandCount++;
                flood($matrix, $i, $j);
            }
        }
    }
    return $islandCount;
}

What do you think about traversing a 2D matrix? Let me know.