You are given an image represented by an m x n grid of integers image, where image[i][j] represents the pixel value of the image. You are also given three integers sr, sc, and color. Your task is to perform a flood fill on the image starting from the pixel image[sr][sc].
To perform a flood fill:
color.Return the modified image after performing the flood fill.
Example 1:
Input: image = [[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]]
Explanation:
From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color.
Note the bottom corner is not colored 2, because it is not horizontally or vertically connected to the starting pixel.
Example 2:
Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0
Output: [[0,0,0],[0,0,0]]
Explanation:
The starting pixel is already colored with 0, which is the same as the target color. Therefore, no changes are made to the image.
Constraints:
m == image.lengthn == image[i].length1 <= m, n <= 500 <= image[i][j], color < 2160 <= sr < m0 <= sc < nThis approach uses recursion to explore all connected pixels that need to be updated. Starting from the initial pixel, you recursively attempt to update all four possible directions (up, down, left, right) whenever the neighboring pixel has the same original color.
The recursion ensures that all connected and valid pixels are eventually updated. Make sure to handle the base case where the function stops if the pixel is out of bounds or if it doesn't need updating (either because it's already updated or has a different color).
In this Python solution, we define a recursive function dfs which updates the color of a pixel and then recursively calls itself for each adjacent pixel. The function checks boundary conditions and whether the pixel is of the original color before updating it.
C
C++
Java
C#
JavaScript
Time Complexity: O(m * n) because in the worst case, all of the pixels will be connected and thus changed.
Space Complexity: O(m * n) due to the recursion call stack.
This approach employs an iterative breadth-first search (BFS) using a queue. Starting from the initial pixel, we enqueue it and begin the BFS process, updating connected pixels of the same original color to the new color.
For each pixel, check its adjacent pixels and enqueue them if they are valid and of the original color. This continues until the queue is empty, ensuring all pixels are updated appropriately.
This Python solution uses a queue to implement the BFS process, iterating over each pixel and its adjacent pixels. The queue ensures all connected pixels are enqueued and processed correctly.
C
C++
Java
C#
JavaScript
Time Complexity: O(m * n), where m and n are the dimensions of the image (same as DFS).
Space Complexity: O(m * n), as we may store all pixels in the queue in the worst-case scenario.
| Approach | Complexity |
|---|---|
| Recursive Depth-First Search (DFS) Approach | Time Complexity: O(m * n) because in the worst case, all of the pixels will be connected and thus changed. |
| Iterative Breadth-First Search (BFS) Approach | Time Complexity: O(m * n), where m and n are the dimensions of the image (same as DFS). |
G-9. Flood Fill Algorithm | C++ | Java • take U forward • 309,202 views views
Watch 9 more video solutions →Practice Flood Fill with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor