Algorithms: The number of Islands Problem in Swift

Subscribe to my newsletter and never miss my upcoming articles

Hello guys and girls, Leo here.

I know it's been a while we don't solve any algorithm problem so today we're continuing the algo series. We'll solve a leetcode problem called "The Number of Islands".

Let's code!

The problem

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:

var islands = [  ["1","1","1","1","0"],   
                 ["1","1","0","1","0"], 
                 ["1","1","0","0","0"],
                 ["0","0","0","0","0"]
] // should be 1 the answer

The Answer:

func numIslands(_ grid: [[Character]]) -> Int {

    var result = 0
    var notGrid = grid
    for row in 0..<grid.count {
        for column in 0..<notGrid[row].count {
            if notGrid[row][column] == "1" {
                result += 1
                islandSearchDFS(&notGrid, row, column)
            }
        }
    }
    return result
}

func islandSearchDFS(_ grid: inout [[Character]],_ row: Int, _ column: Int) {
    if row < 0 || row>=grid.count || column < 0 || column>=grid[row].count || grid[row][column] == "0"{
        return
    } // 1

    grid[row][column] = "0" // visited island //2

    islandSearchDFS(&grid, row-1, column)  //3
    islandSearchDFS(&grid, row+1, column) //3
    islandSearchDFS(&grid, row, column-1) //3
    islandSearchDFS(&grid, row, column+1) //3
}

In this solution we used Depth first search, this means that we'll traverse the graph not in layer but all the way in one direction.

The func islandSearchDFS is straightforward.

  1. First we check if we are in the 2D array boundaries, and also checks if the actual item is already a "visited one".
  2. Turn the actual node 1 into 0, so we visit the node so we don't count again and avoid [infinity recursion] en.wikipedia.org/wiki/Infinite_loop#Infinit..).
  3. Now we recursively check all the neighbours (first all upper nodes, all down nodes, all left nodes, and finally all right nodes) of the node trying to find the extension of the island.

And that's it. Hope you enjoy this simple but very useful algo.

Thanks for the reading and... That's all folks!

image credit: image

No Comments Yet