54. Flood Fill

EasyGraphs: BFS & DFSAlso on LeetCode ↗

Starting from pixel (sr, sc), repaint it and every pixel connected to it (4-directionally) with the same original colour using color. Return the image.

Example 1

Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2

Output: [[2,2,2],[2,2,0],[2,0,1]]

Example 2

Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0

Output: [[0,0,0],[0,0,0]]

Hint 1

DFS from the start pixel, only stepping onto pixels with the original colour.

Hint 2

If the new colour equals the old one, return immediately.

GraphDFSMatrix

Reference solution for DFS (time O(m · n), space O(m · n)). Each solution passes every test in all four languages.

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
        old = image[sr][sc]
        if old == color:
            return image                 # nothing to do (and avoids an infinite loop)
        def fill(r, c):
            if 0 <= r < len(image) and 0 <= c < len(image[0]) and image[r][c] == old:
                image[r][c] = color
                fill(r + 1, c); fill(r - 1, c); fill(r, c + 1); fill(r, c - 1)
        fill(sr, sc)
        return image

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int color) {
        if (image[sr][sc] != color) fill(image, sr, sc, image[sr][sc], color);
        return image;
    }
    private void fill(int[][] img, int r, int c, int old, int color) {
        if (r < 0 || c < 0 || r >= img.length || c >= img[0].length || img[r][c] != old) return;
        img[r][c] = color;
        fill(img, r + 1, c, old, color); fill(img, r - 1, c, old, color);
        fill(img, r, c + 1, old, color); fill(img, r, c - 1, old, color);
    }
}

class Solution {
    void fill(vector<vector<int>>& img, int r, int c, int old, int color) {
        if (r < 0 || c < 0 || r >= (int)img.size() || c >= (int)img[0].size() || img[r][c] != old) return;
        img[r][c] = color;
        fill(img, r + 1, c, old, color); fill(img, r - 1, c, old, color);
        fill(img, r, c + 1, old, color); fill(img, r, c - 1, old, color);
    }
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        if (image[sr][sc] != color) fill(image, sr, sc, image[sr][sc], color);
        return image;
    }
};

function floodFill(image, sr, sc, color) {
  const old = image[sr][sc];
  if (old === color) return image;
  const fill = (r, c) => {
    if (r < 0 || c < 0 || r >= image.length || c >= image[0].length || image[r][c] !== old) return;
    image[r][c] = color;
    fill(r + 1, c); fill(r - 1, c); fill(r, c + 1); fill(r, c - 1);
  };
  fill(sr, sc);
  return image;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Language

54. Flood Fill

Example 1

Example 2

Approach 1: DFS ✅