Flood fill Algorithm

JavaView on GFG

Time: O(n*m)

Space: O(n*m)

Intuition

From a starting pixel, paint it and all connected pixels of the same color with a new color. DFS/BFS from start.

Algorithm

1If starting pixel's color already equals new color, return (avoid infinite loop).
2DFS from (sr,sc): set image[r][c]=newColor. Recurse on 4 neighbors with old color.

Example Walkthrough

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

1.Fill connected 1s: (0,0),(0,1),(0,2),(1,0),(1,1),(2,0) become 2.

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

Common Pitfalls

•Check if start pixel's color == new color and skip to avoid infinite recursion.

Flood fill Algorithm.java

Java

// Approach: DFS/BFS from source pixel. Replace all connected pixels of the old color with new color.
// Time: O(n*m) Space: O(n*m)
import java.util.*;

class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int n = image.length, m = image[0].length;
        boolean[][] visited = new boolean[n][m];
        int[][] direction = { { 0, -1 }, { -1, 0 }, { 0, 1 }, { 1, 0 } };
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(sr, sc));

        while (!q.isEmpty()) {
            Node curr = q.remove();
            visited[curr.row][curr.col] = true;
            for (int[] dir : direction) {
                int newRow = dir[0] + curr.row;
                int newCol = dir[1] + curr.col;
                if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < m &&
                        image[newRow][newCol] == image[sr][sc] && !visited[newRow][newCol]) {
                    image[newRow][newCol] = newColor;
                    q.add(new Node(newRow, newCol));
                }
            }
        }
        image[sr][sc] = newColor;
        return image;
    }
}

class Node {
    int row, col;

    public Node(int row, int col) {
        this.row = row;
        this.col = col;
    }
}

Was this solution helpful?