733. Flood Fill

DFS

class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color)
    {
        int originalColor = image[sr][sc];
        if (color == originalColor) return image;
        dfs(image, sr, sc, color, originalColor);
        return image;
    }

    void dfs(vector<vector<int>>& image, int i, int j, int color, int originalColor)
    {
        if (i < 0 || j < 0 || i >= image.size() || j >= image[0].size() || image[i][j] == color || image[i][j] != originalColor)
            return;

        image[i][j] = color;

        vector<vector<int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        for (const auto& dir : directions)
        {
            dfs(image, i + dir[0], j + dir[1], color, originalColor);
        }
    }
};

• T: $O(M \cdot N)$
• S: $O(1)$