Traversing a 2D Matrix

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 &lt; $iSize; $i++) {
        $jSize = count($matrix[$i]);
        for ($j = 0; $j &lt; $jSize; $j++) {
            if (isIslandCell($matrix[$i][$j])) {
                $islandCount++;
                flood($matrix, $i, $j);
            }
        }
    }
    return $islandCount;
}

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;

}

The function iterates over the 2D array using a nested for loop. If the inner loop finds an “island cell” (value equals to 1), the island counter is incremented and starts flooding through the matrix:

function flood(array &amp;$matrix, int $i, int $j) {
    $matrix[$i][$j] = 0;
    consider($matrix, $i + 1, $j);
    consider($matrix, $i, $j + 1);
    consider($matrix, $i - 1, $j);
    consider($matrix, $i, $j - 1);
}

function flood(array &$matrix, int $i, int $j) {

$matrix[$i][$j] = 0;

consider($matrix, $i + 1, $j);

consider($matrix, $i, $j + 1);

consider($matrix, $i - 1, $j);

consider($matrix, $i, $j - 1);

}

The first line unsets the current cell to a 0 (“water”). Notice how the matrix is passed to the method (by reference). We then consider N/S/E/W of the cell with:

function consider(array &amp;$matrix, int $i, int $j) {
    $iSize = count($matrix);
    if (inRange($i, 0, $iSize)) {
        $jSize = count($matrix[$i]);
        if (inRange($j, 0, $jSize)) {
            if (isIslandCell($matrix[$i][$j])) {
                flood($matrix, $i, $j);
            }
        }
    }
}

function consider(array &$matrix, int $i, int $j) {

$iSize = count($matrix);

if (inRange($i, 0, $iSize)) {

$jSize = count($matrix[$i]);

if (inRange($j, 0, $jSize)) {

if (isIslandCell($matrix[$i][$j])) {

flood($matrix, $i, $j);

}

If i and j are in the range and the current cell is a 1, we go further with flooding for all other neighbors.

Here are the inRange() and isIslandCell() methods for being complete:

function isIslandCell(int $val) {
    return 1 === $val;
}

function inRange(int $i, int $start, int $end) {
    return $i &gt;= $start &amp;&amp; $i &lt; $end;
}

function isIslandCell(int $val) {

return 1 === $val;

}

function inRange(int $i, int $start, int $end) {

return $i >= $start && $i < $end;

}

Graph Traversing

So far, we talked about traversing 2D matrices. But what is about graphs? Since we talk about DFS, there must be a graph based solution as well. Based on the following graph:

traversing matrix: connected nodes — Graph with 3 Sub Graphs

let’s have a look what this looks like:

function countIslands(AbstractGraph $graph): int {
    if (null === $graph-&gt;getNodes()) return 0;
    $c = 0;
    $v = new ArrayList();

    foreach ($graph-&gt;getNodes() as $node) {
        if ($v-&gt;containsValue($node)) continue;
        $c++;
        flood($node, $v);
    }
    return $c;
}

function flood(Node $node, ArrayList &amp;$v): void {
    foreach ($node-&gt;getAdjacents() as $adjacent) {
        if ($v-&gt;containsValue($adjacent)) continue;
        $v-&gt;add($adjacent);
    }
}

function countIslands(AbstractGraph $graph): int {

if (null === $graph->getNodes()) return 0;

$c = 0;

$v = new ArrayList();

foreach ($graph->getNodes() as $node) {

if ($v->containsValue($node)) continue;

$c++;

flood($node, $v);

}

return $c;

}

function flood(Node $node, ArrayList &$v): void {

foreach ($node->getAdjacents() as $adjacent) {

if ($v->containsValue($adjacent)) continue;

$v->add($adjacent);

}

Since there is no “water” in a graph (no indices with 0 values), we cannot use 1’s and 0’s to distinguish between nodes and “the rest” and specify which node is already visited. Instead we iterate over all nodes and flood all neighbors/adjacents (like DFS just works). Since it is not possible to switch 1’s to 0’s, it is not necessary to use a visited list.

EDIT 11/14/2020

There is an easier method of the array based method utilizing DFS. The following code is the same as the first example code:

<?php 
function numIslands(array $grid):int {
    $length      = count($grid);
    $islandCount = 0;

    if ($length === 0) {
        return 0;
    }

    for ($i = 0; $i < $length; $i++) {
        $jCount = count($grid[$i]);
        for ($j = 0; $j < $jCount; $j++) {

            if ($grid[$i][$j] === '1') {
                $islandCount++;
                dfs($grid, $i, $j);
            }
        }
    }

    return $islandCount;
}

function dfs(array &$grid, int $i, int $j): void {
    $iLength = count($grid);
    $jLength = count($grid[0] ?? []);

    if ($i < 0 || $j < 0 || $i >= $iLength || $j >= $jLength || $grid[$i][$j] === '0') {
        return;
    }

    $grid[$i][$j] = '0';
    dfs($grid, $i - 1, $j);
    dfs($grid, $i + 1, $j);
    dfs($grid, $i, $j - 1);
    dfs($grid, $i, $j + 1);
}

<?php

function numIslands(array $grid):int {

$length = count($grid);

$islandCount = 0;

if ($length === 0) {

return 0;

}

for ($i = 0; $i < $length; $i++) {

$jCount = count($grid[$i]);

for ($j = 0; $j < $jCount; $j++) {

if ($grid[$i][$j] === '1') {

$islandCount++;

dfs($grid, $i, $j);

}

return $islandCount;

}

function dfs(array &$grid, int $i, int $j): void {

$iLength = count($grid);

$jLength = count($grid[0] ?? []);

if ($i < 0 || $j < 0 || $i >= $iLength || $j >= $jLength || $grid[$i][$j] === '0') {

return;

}

$grid[$i][$j] = '0';

dfs($grid, $i - 1, $j);

dfs($grid, $i + 1, $j);

dfs($grid, $i, $j - 1);

dfs($grid, $i, $j + 1);

}

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