C++: Flood Fill

Thought Process

The problem involves performing a flood fill operation on an image represented as a 2D grid using Depth-First Search (DFS) traversal. We start from a given pixel(sr, sc) and change its color to the newColor. We then recursively apply the same operation to all adjacent pixels(up, down, left, right) that have the same color as the starting pixel. We need to ensure that we handle edge cases, such as going out of bounds or when the new color is the same as the old color, to avoid infinite recursion. 

class Solution {
public:
    void dfs(vector<vector<int>>& image, int sr, int sc, int oldColor, int newColor){

        if(sr>=image.size() || sr<0 || sc>=image[0].size() || sc<0 || image[sr][sc]!=oldColor ||
 image[sr][sc]==newColor){
            return;
        }

        // Color the pixel and try to traverse in all 4 directions.
        image[sr][sc]=newColor;
        dfs(image,sr+1,sc,oldColor,newColor);
        dfs(image,sr-1,sc,oldColor,newColor);
        dfs(image,sr,sc+1,oldColor,newColor);
        dfs(image,sr,sc-1,oldColor,newColor);
    }
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
        
        int oldColor = image[sr][sc];
        dfs(image,sr,sc,oldColor,newColor);

        return image;
    }
};

Code Complexity

Time Complexity: O(n)

The algorithm visits each pixel in the image once, making it linear in time complexity, where 'n' is the total number of pixels in the image.

Space Complexity: O(h)

The space complexity is determined by the depth of the recursion stack, which can go up to 'h', where 'h' is the height of the recursion tree. In the worst case, it can be O(n) if the image is filled with the same color.

Code copied!