DSA

Flood Fill

Graphs. Time O(mxn), Space O(mxn).

August 8, 2026
DSAGraphsBFSDFSLeetCodePractice

Practice Link

BFS#

Flood fill is a classic connected-component recolouring problem. Starting from the given pixel (sr, sc), we need to recolour every pixel that is reachable via 4-directional adjacency and shares the original colour. BFS naturally expands outward layer by layer from the source pixel: we enqueue (sr, sc), then for each dequeued pixel we immediately paint it the new colour and enqueue any unvisited 4-directional neighbour that still holds the original colour. The early-exit guard if (image[sr][sc] == color) return image prevents an infinite loop when the source pixel already has the target colour — without it every newly painted neighbour would be re-enqueued endlessly.

Implementation - BFS#

cpp
class Solution {
public:
    vector<int> dx = {0,0,1,-1};
    vector<int> dy = {1,-1,0,0};
    bool isValidCell(vector<vector<int>>& grid, int x, int y)
    {
        if(x<0 || x>=grid.size() || y<0 || y>= grid[0].size())
            return false;
        return true;
    }
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        int m = image.size();
        int n = image[0].size();

        if(image[sr][sc] == color)
            return image;

        queue<pair<int,int>> q;
        q.push({sr,sc});

        int initColor = image[sr][sc];

        while(!q.empty())
        {
            int row = q.front().first;
            int col = q.front().second;
            q.pop();

            image[row][col] = color;

            for(int dir=0;dir<4;dir++)
            {
                int newRow = row + dx[dir];
                int newCol = col + dy[dir];

                if(isValidCell(image, newRow, newCol) && image[newRow][newCol]==initColor)
                    q.push({newRow, newCol});
            }
        }
        return image;
    }
};

DFS#

The DFS variant achieves the same result recursively: paint the current pixel, then recurse into each valid 4-directional neighbour that still holds the original colour. Because we paint the pixel before recursing, a neighbour that was already painted won't match originalColor, naturally preventing revisits without a separate visited array. Both BFS and DFS touch every pixel in the connected component exactly once, giving identical O(m×n) time and space, but DFS risks a stack-overflow on very large fully-connected grids whereas BFS uses an explicit queue on the heap.

Implementation - DFS#

cpp
class Solution {
public:
    vector<int> dx={1,0,-1,0};
    vector<int> dy={0,1,0,-1};

    void DFS(vector<vector<int>>& image, int x, int y, int newColor, int originalColor)
    {
        if(image[x][y] == newColor)
            return;

        image[x][y] = newColor;

        for(int k=0;k<4;k++)
        {
            int nx = x + dx[k];
            int ny = y + dy[k];
            if(nx>=0 && nx<image.size() && ny>=0 && ny<image[0].size() && image[nx][ny] == originalColor)
            {
                DFS(image,nx,ny, newColor, originalColor);
            }
        }
    }

    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {

        if(image[sr][sc] == color)
            return image;
        DFS(image,sr,sc, color, image[sr][sc]);
        return image;
    }
};

Time Complexity: O(mxn)

Space Complexity: O(mxn)

Related articles

DSAMax Area of IslandDFS flood-fill to find the largest connected island. Time O(m×n), Space O(m×n).DSANumber of Ways to Arrive at DestinationGraphs. Time O(m log n), Space O(m+n).DSAWord SearchDFS - Backtracking approach. Optimal — Time O(mn * 4^L), Space O(1).