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“.

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:

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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 | 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:

1 2 3 4 5 6 7 | 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:

1 2 3 4 5 6 7 8 9 10 11 | 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:

1 2 3 4 5 6 7 | 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:

let’s have a look what this looks like:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | 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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | <?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); } |