Skip to content

733. Flood Fill 👍

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc,
                                int newColor) {
    dfs(image, sr, sc,
        vector<vector<bool>>(image.size(), vector<bool>(image[0].size())),
        image[sr][sc], newColor);
    return image;
  }

 private:
  void dfs(vector<vector<int>>& image, int i, int j,
           vector<vector<bool>>&& seen, int startColor, int newColor) {
    if (i < 0 || i == image.size() || j < 0 || j == image[0].size())
      return;
    if (image[i][j] != startColor || seen[i][j])
      return;

    image[i][j] = newColor;
    seen[i][j] = true;

    dfs(image, i + 1, j, std::move(seen), startColor, newColor);
    dfs(image, i - 1, j, std::move(seen), startColor, newColor);
    dfs(image, i, j + 1, std::move(seen), startColor, newColor);
    dfs(image, i, j - 1, std::move(seen), startColor, newColor);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
    boolean[][] seen = new boolean[image.length][image[0].length];
    dfs(image, sr, sc, seen, image[sr][sc], newColor);
    return image;
  }

  private void dfs(int[][] image, int i, int j, boolean[][] seen, int startColor, int newColor) {
    if (i < 0 || i == image.length || j < 0 || j == image[0].length)
      return;
    if (image[i][j] != startColor || seen[i][j])
      return;

    image[i][j] = newColor;
    seen[i][j] = true;

    dfs(image, i + 1, j, seen, startColor, newColor);
    dfs(image, i - 1, j, seen, startColor, newColor);
    dfs(image, i, j + 1, seen, startColor, newColor);
    dfs(image, i, j - 1, seen, startColor, newColor);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
  def floodFill(self, image: list[list[int]],
                sr: int, sc: int, newColor: int) -> list[list[int]]:
    startColor = image[sr][sc]
    seen = set()

    def dfs(i: int, j: int) -> None:
      if i < 0 or i == len(image) or j < 0 or j == len(image[0]):
        return
      if image[i][j] != startColor or (i, j) in seen:
        return

      image[i][j] = newColor
      seen.add((i, j))

      dfs(i + 1, j)
      dfs(i - 1, j)
      dfs(i, j + 1)
      dfs(i, j - 1)

    dfs(sr, sc)
    return image