Flood Fill

easy array dfs bfs matrix

Problem

Given an m×n image grid, a starting pixel (sr, sc), and a new color, recolor the connected region of pixels that share the starting pixel's original color (4-directionally connected) to the new color.

Inputimage = [[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]]

All pixels orthogonally connected to (1,1) and equal to 1 become 2.

image rows (semicolon-separated, comma cells)

new color

def flood_fill(image, sr, sc, color):
    start = image[sr][sc]
    if start == color:
        return image
    m, n = len(image), len(image[0])
    def dfs(r, c):
        if r < 0 or r >= m or c < 0 or c >= n or image[r][c] != start:
            return
        image[r][c] = color
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)
    dfs(sr, sc)
    return image

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

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

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

Explanation

This is exactly like the paint bucket tool in an image editor: click a pixel and every connected pixel of the same color gets recolored. We do it with a simple depth-first search (DFS) that spreads out from the seed cell.

First we remember the seed's start color. If that already equals the new color, there is nothing to do (and skipping it also avoids an infinite recursion). Otherwise we kick off dfs(sr, sc).

Each dfs(r, c) call first checks if we've stepped off the grid or onto a cell that isn't the original color — if so it returns immediately. Otherwise it repaints the current cell to the new color and recursively visits its four neighbors: up, down, left, and right.

Because we overwrite a cell's color the moment we visit it, that cell no longer matches start, so it naturally won't be revisited — that's what stops the spread at the region's borders.

Example: in [[1,1,1],[1,1,0],[1,0,1]] starting at (1,1) with color 2, the search flows through all the connected 1s, turning them into 2s while the isolated 1 at the bottom-right is left untouched.

Time: O(m·n) Space: O(m·n)