A.I, Data and Software Engineering

Number of Islands solution


In this post, we have a look at using a queue and breath-first search algorithm to solve a Leetcode challenge. The problem is stated as follows.

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return 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 1:

Input: grid = [
Output: 1

Queue and BFS


In a FIFO data structure, the first element added to the queue will be processed first.

As shown in the picture above, the queue is a typical FIFO data structure. The insert operation is also called enqueue and the new element is always added at the end of the queue. The delete operation is called dequeue. You are only allowed to remove the first element.

Solution with bfs

The purpose of the breadth-first search is to write down all the branches when facing a junction and then choose one of them to enter, Then record its shunting situation, and then return to another fork, and repeat the operation.

The pseudo-code looks like this:

 1  procedure BFS(G, root) is
 2      let Q be a queue
 3      label root as explored
 4      Q.enqueue(root)
 5      while Q is not empty do
 6          v := Q.dequeue()
 7          if v is the goal then
 8              return v
 9          for all edges from v to w in G.adjacentEdges(v) do
10              if w is not labeled as explored then
11                  label w as explored
12                  Q.enqueue(w)

Kotlin implementation

class Solution {
    fun numIslands(grid: Array<CharArray>): Int {
        //find 1 and expands until there is no more 1 connected horizontally and vertically
        //increase by 1
        var result = 0
        val queue: Queue<Pair<Int, Int>> = LinkedList<Pair<Int, Int>>()

        for(r in grid.indices){
            for (c in grid[0].indices){
                if(grid[r][c] == '1'){
                    result += 1
                    queue.add(Pair(r, c))
                    grid[r][c] = '0' //visited
                        val (x, y) = queue.poll()
                        if(x > 0 && grid[x-1][y] == '1') //compare the left
                            grid[x-1][y] = '0'
                            queue.add(Pair(x-1, y))
                        if(x < grid.lastIndex && grid[x+1][y] == '1') //compare the right
                            grid[x+1][y] = '0'
                            queue.add(Pair(x+1, y))
                        if(y > 0 && grid[x][y - 1] == '1') //compare the top
                            grid[x][y - 1] = '0'
                            queue.add(Pair(x, y - 1))
                        if(y < grid[0].lastIndex  && grid[x][y + 1] == '1') //compare the bottom
                            grid[x][y + 1] = '0'
                            queue.add(Pair(x, y + 1))
        return result

For more algorithm articles, please go here.

Add comment


A.I, Data and Software Engineering

PetaMinds focuses on developing the coolest topics in data science, A.I, and programming, and make them so digestible for everyone to learn and create amazing applications in a short time.