Number of islands problem Leetcode recursive DFS and non recursive BFS

Question

I was trying to fix the following leetcode problem using a recursive DFS approach and a non-recursive BFS approach. Both work, but the recursive DFS one is 3 ms fast vs the non-recursive BFS which is 6 ms. Can someone please explain me why the DFS one is faster and let me know of ways to improve the BFS code.

Leetcode problem description:

200. Number of Islands

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

===================================================

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

    for(int i=0; i<grid.length; i++){
        for(int j=0; j<grid[i].length; j++){
            if(grid[i][j]=='1'){
                count+=1;
                callBFS(grid, i, j); //can be replaced with callDFS
            }
        }
    }
    return count;
}

private static void callDFS(char[][] grid, int i, int j ) {
    if(i<0 || i>=grid.length || j<0 || j>=grid[i].length || grid[i][j]=='0'){
        return;
    }
    grid[i][j]='0';

    callDFS(grid, i+1, j);
    callDFS(grid, i-1, j);
    callDFS(grid, i, j-1);
    callDFS(grid, i, j+1);
}

private static void callBFS(char[][] grid, int i, int j ) {
    java.util.Queue<Pair<Integer, Integer>> myQueue = new LinkedList<>();

    Pair<Integer, Integer> initialPair = new Pair<>(i, j);
    myQueue.add(initialPair);

    while(!myQueue.isEmpty()){
        Pair<Integer, Integer> tempPair = myQueue.poll();
        int row = tempPair.getKey();
        int col = tempPair.getValue();
        if(grid[tempPair.getKey()][tempPair.getValue()]=='1'){
            grid[tempPair.getKey()][tempPair.getValue()]='0';
            if(row+1<grid.length && grid[row+1][col]=='1'){
                myQueue.add(new Pair<>(row+1, col));
            }
            if(row-1>=0 && grid[row-1][col]=='1'){
                myQueue.add(new Pair<>(row-1, col));
            }
            if(col-1>=0 && grid[row][col-1]=='1'){
                myQueue.add(new Pair<>(row, col-1));
            }
            if(col+1<grid[row].length && grid[row][col+1]=='1'){
                myQueue.add(new Pair<>(row, col+1));
            }
        }
    }
}

I was expecting both the DFS and BFS approach will run in a very simillar speed.

Answer 1

I was expecting both the DFS and BFS approach will run in a very similar speed.

Actually, as one runs twice as fast as the other, their running times have the same order of magnitude, and "just" differ by a factor 2.

The BFS code has some overhead that occurs for each "visit" of a cell:

• Adding and polling from a queue
• Pairing and unpairing of coordinates

The overhead of DFS consists mostly of the internal call stack management, which is expected to be faster than an explicit queue implementation.

We can however try to optimise a bit:

• Use an ArrayDeque instead of LinkedList
• Replace Pair<Integer, Integer> with just Integer, and combine coordinates with a simple formula into unique integers.
• Set grid[row][col] to 0 when you add a cell to the queue, instead of doing that when you poll from the queue. This avoids putting the same cell on the queue multiple times, keeping the queue a bit shorter.

Here is the updated BFS code:

private static void callBFS(char[][] grid, int i, int j ) {
    int n = grid.length;
    int m = grid[0].length;
    java.util.Queue<Integer> myQueue = new ArrayDeque<>();

    grid[i][j] = '0';
    myQueue.add(i * m + j);

    while (!myQueue.isEmpty()) {
        int tempPair = myQueue.poll();
        int row = tempPair / m;
        int col = tempPair % m;
        if (row+1 < n && grid[row+1][col] == '1') {
            grid[row+1][col] = '0';
            myQueue.add(tempPair + m);
        }
        if (row > 0 && grid[row-1][col] == '1') {
            grid[row-1][col] = '0';
            myQueue.add(tempPair - m);
        }
        if (col > 0 && grid[row][col-1] == '1') {
            grid[row][col-1] = '0';
            myQueue.add(tempPair - 1);
        }
        if (col+1 < m && grid[row][col+1] == '1') {
            grid[row][col+1] = '0';
            myQueue.add(tempPair + 1);
        }
    }
}

Still, the queue overhead is there, making it a bit slower than the recursion-based DFS algorithm.