Algorithms: Number of Islands Problem in Swift

Hello guys and girls, Leo here. Today we’ll solve a leetcode problem called “The Number of Islands” using DFS.

I know it’s been a while since we don’t solve any algorithm problem so today we’re continuing the algorithm series.

Let’s code!

Number of Islands Problem – Using DFS to solve

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 surrounded by water.

For example:

var islands = [ ["1","1","1","1","0"],
                ["1","1","0","1","0"],
                ["1","1","0","0","0"],
                ["0","0","0","0","0"]
]

For the above input, the answer should be 1.

The Answer:

Check the answer below:

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, which means that we’ll traverse the graph going max deep for each children node instead of traversing all the children layer.

The function islandSearchDFS is straightforward.

1. First, we check if we are in the 2D array boundaries, and also check 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.
3. Now we recursively check all the neighbors (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 algorithm.

Algorithms: Continue Studying

Using Swift is a real joy because it is made to make hard things possible. If you ever wondered if you could implement your own Iterator protocol to create a linked list, yes you can. There you will learn to create a linked list using the Swift Iterator protocol.

This is one of three most famous linked lists algorithms, how to reverse a linked list iteratively. It is crucial for algorithm interviews to know this simple concept in Swift and you can learn it in that article.

Summary

Today we learn how to solve the Number of Islands Problem using DFS in Swift. DFS and BFS are powerful techniques that enable us to solve various classes of problems, it is not an understatement that if you master DFS and BFS you could solve most common graphs problems.

That’s all my people, I hope you liked reading this article as much as I enjoyed writing it. If you want to support this blog you can Buy Me a Coffee or leave a comment saying hello. You can also sponsor posts and I’m open to freelance writing! You can reach me on LinkedIn or Twitter and send me an e-mail through the contact page.

Thanks for the reading and… That’s all folks.

Credits – image