Leetcode: Number of Islands - BFS (Queue vs Recursion)

Question

I was playing around with leetcode's Number of Islands. As per the challenge's description:

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 = [
   ["1","1","1","1","0"],
   ["1","1","0","1","0"],
   ["1","1","0","0","0"],
   ["0","0","0","0","0"]
]
Output: 1

Example 2:

Input: grid = [
   ["1","1","0","0","0"],
   ["1","1","0","0","0"],
   ["0","0","1","0","0"],
   ["0","0","0","1","1"]
]
Output: 3

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.

I went for a BFS solution, using a queue. It yielded in 8ms (beats 10.81%) on leetcode. I then tried another BFS approach using recursion this time, and it yielded in 2ms (beats 85.39%) this time.

Q: Why is the recursive method faster than the one using the queue?

Here are both BFS using queue / BFS using recursion code (java):

BFS (Queue)

// Directions: Down, right, Up, left - ie incrementing either row index or col index
private static final int[][] directions = {
   {1, 0}, // Down 1 row
   {0, 1}, // Right 1 col
   {-1, 0}, // Up 1 row
   {0, -1} // left 1 col
};

public static int numIslands(char[][] grid) {
   Queue<int[]> queue = new LinkedList<>();
   int nbOfIslands = 0;

   //loop matrix
   for (int i = 0; i < grid.length; i++) {
       for (int j = 0; j < grid[0].length; j++) {
           if (grid[i][j] == '1') {
              // Concept: Each BFS is one island, so on first encounter of a '1' 
              // You know you have one new island so you increment total number 
              // of islands, then go to BFS to mark all remaining '1's in this island as visited.
              nbOfIslands++;


              //BFS using queue
              //Mark current cell as visited
              grid[i][j] = '2';// you can mark it as '0' or anything you want; except '1'
              queue.add(new int[]{i, j});// add [row,col]

              while (!queue.isEmpty()) {
                int[] rcPair = queue.remove();//dequeue and get first [row,col] pair
                // go up, down, left , right to mark as visited where it is '1'
                for (int[] direction : directions) {
                  int new_row = rcPair[0] + direction[0];
                  int new_col = rcPair[1] + direction[1];
                  if (new_row >= 0 && new_row < grid.length
                       && new_col >= 0 && new_col < grid[0].length
                       && grid[new_row][new_col] == '1') {
                          queue.add(new int[]{new_row, new_col});
                          grid[new_row][new_col] = '2';
                  }
                }
               }//end while
            }
          }
    }

   return nbOfIslands;
}

BFS (Recursion)

// Directions: Down, right, Up, left - ie incrementing either row index or col index
private static final int[][] directions = {
   {1, 0}, // Down 1 row
   {0, 1}, // Right 1 col
   {-1, 0}, // Up 1 row
   {0, -1} // left 1 col
};

public static int numIslands(char[][] grid) {
   int nbOfIslands = 0;

   //loop matrix
   for (int i = 0; i < grid.length; i++) {
       for (int j = 0; j < grid[0].length; j++) {
           if (grid[i][j] == '1') {
              // Concept: Each BFS is one island, so on first encounter of a '1' 
              // You know you have one new island so you increment total number 
              // of islands, then go to BFS to mark all remaining '1's in this island as visited.
              nbOfIslands++;

              //BFS Using recursion
              bfs(grid, i, j);//grid,row,col
            }
         }
     }

   return nbOfIslands;
}

// Method copied from another user on leetcode, to test difference.
public static void bfs(char[][] grid, int row, int col) {
        // Mark the current cell so it won't be revisited.
        grid[row][col] = '2';

        // Recursively visit all adjacent cells that are part of the island ('1').
        if (row > 0 && grid[row - 1][col] == '1')
            bfs(grid, row - 1, col);
        if (row + 1 < grid.length && grid[row + 1][col] == '1')
            bfs(grid, row + 1, col);
        if (col > 0 && grid[row][col - 1] == '1')
            bfs(grid, row, col - 1);
        if (col + 1 < grid[0].length && grid[row][col + 1] == '1')
            bfs(grid, row, col + 1);
 }

Answer 1

Performance

• Figures

First of all, regarding these figures in milliseconds.

They can be useful, to indicate whether something is wrong with the algorithm, but they can hardly be considered accurate. Because it's not feasible for Leetcode to run proper benchmarks which take into account JVM warm up allowing JIT compilation to kick in and then measure the performance of the optimized code (because it'll take forever). These figures are imprecise, naïve measurements that might even be affected by the load that a server experiences at the moment.

• Data structures

Recursive code, basically, relies on the JVM call stack as a data structure. The call stack is a vital component of the JVM, optimized for efficient method invocation and storing frames representing method invocations as contiguous blocks of memory.

^{A word of caution: utilizing recursion might result in a StackOverflowError}

On the other hand, your iterative implementation makes use of a LinkedList.

A LinkedList is a swarm of nodes scattered across the JVM's Heap. It lacks data-locality, jumping between memory locations that host different nodes is costful. Hence, even remove() and add() operations on a LinkedList nominally have time complexity \$\mathcal{O}(1)\$, they are no match for the speed of the call stack.

• Choosing proper Queue implementation

You can improve performance of the iterative solution by replacing the LinkedList with an ArrayDeque.

As its name suggests an ArrayDeque is backed by an array, hence internal data store of this collection occupies a contiguous block of memory. Because of that it's easy to predict the memory location of the next element in an ArrayDeque, and it performs adding and removing elements faster in comparison with a LinkedList.

Algorithm

The algorithm might be slightly improved by using Depth-first search to traverse the disjointed components of the graph (islands) instead of Breadth-first search.

If we consider the worst case scenario, the maximum size of the queue will be twice larger than the maximum stack size if we were doing Depth-first search instead.

Naming

According to the Java language naming convention, names of static final fields are in upper case (directions -> DIRECTIONS).

nbOfIslands - avoid abbreviations (except for very few well-known like min, max). How about islandCount?

The method name bfs is not a perfect one. Because it doesn't reveal its intent, which is to traverse an island. Instead, it says how it does what it's meant to do. If it were a real world application, a better name will be traverseIsland, the algorithm might be mentioned in the documentation comment.

Code Structure

Extracting logic into separate methods doesn't hurt the performance (the JIT compiler inlines calls that are frequent, and thus crucial for the application efficiency).

No need in writing monstrosities like numIslands().

By placing all logic into one method you are not only sacrificing the readability of the code, but also impeding the optimization of this method (the shorter a method is, the earlier it gets optimized by the JIT compiler).