Flood Fill - DFS vs BFS Detailed Comparison

Description

Note: In this question, if the color of the starting cell is the newColor, we don't paint it again.

This would cause a stack overflow, hence another way to deal with this would be to use a 'visited' set.

Solution 1: Recursive DFS

Time Complexity: O(mn) 84ms
Space Complexity: O(mn) (worst case) 40.9MB

var floodFill = function(image, sr, sc, newColor) {
  const directions = [[-1, 0], [0, 1], [1, 0], [0, -1]];
  let m = image.length, n = image[0].length;
  let color = image[sr][sc];
  if (color !== newColor) dfs(sr, sc); // only if starting cell is not the same color
  return image;
  
  function dfs(row, col) {
    image[row][col] = newColor; // color it with the newColor
    for (var [x, y] of directions) {
      let newX = row + x, newY = col + y;
      if (newX < 0 || newX >= m || newY < 0 || newY >= n || image[newX][newY] !== color) continue;
      dfs(newX, newY);
    }
  }  
};

Solution 2: BFS

Time Complexity: O(mn)
Space Complexity: O(mn) (worst case)

var floodFill = function(image, sr, sc, newColor) {
  const directions = [[-1, 0], [0, 1], [1, 0], [0, -1]];
  let m = image.length, n = image[0].length;
  let color = image[sr][sc];
  if (color === newColor) return image;
  
  let queue = [[sr, sc]];
  image[sr][sc] = newColor;
  
  while (queue.length) {
    let [row, col] = queue.shift();
    for (var [x, y] of directions) {
      let newX = row + x, newY = col + y;
      if (newX < 0 || newX >= m || newY < 0 || newY >= n || image[newX][newY] !== color) continue;
      queue.push([newX, newY]);
      image[newX][newY] = newColor;
    }
  }
  return image;
};

Comparison between bfs and dfs
Both dfs and bfs have the same time complexity,
but for JavaScript, bfs could have a slightly slower runtime due to the .shift() having an O(n) time complexity.
This can be fixed by either using

1. a linked list or
2. using two queues and using .pop() instead of .shift()

javascript