Depth-First Search
Flood Fill
DESCRIPTION (inspired by Leetcode.com)
Given a m x n integer grid image and integers sr, sc, and newColor, write a function to perform a flood fill on the image starting from the pixel image[sr][sc].
In a 'flood fill', start by changing the color of image[sr][sc] to newColor. Then, change the color of all pixels connected to image[sr][sc] from either the top, bottom, left or right that have the same color as image[sr][sc], along with all the connected pixels of those pixels, and so on.
Input:
image = [[1,0,1],[1,0,0],[0,0,1]], sr = 1, sc = 1, color = 2
Output:
[[1,2,1],[1,2,2],[2,2,1]]
The zeroes connected to the starting pixel (1, 1) are colored with the new color (2).
public class Solution {
public int[][] flood_fill(int[][] image, Integer sr, Integer sc, Integer color) {
// Your code goes here
}
}Run your code to see results here
Have suggestions or found something wrong?
Explanation
This solution uses depth-first search to traverse the grid and perform the flood fill by defining a recursive function dfs that takes in the current row and column of the pixel being explored. Each call to dfs will either change the color of the pixel if the pixel is the same color as the starting pixel, and then recursively call dfs on its connected pixels. If the pixel is not the same color as the starting pixel, the function will return without doing anything.
The algorithm starts at the given starting pixel and uses depth-first search to explore all pixels connected 4-directionally to it. At each pixel, it first checks to see if the pixel is the same color as the starting pixel. If it is, it changes the color of the pixel and continues to explore the connected pixels.
public static int[][] floodFill(int[][] image, int sr, int sc, int color) {int rows = image.length;int cols = image[0].length;int originalColor = image[sr][sc];if (originalColor == color) {return image;}dfs(image, sr, sc, originalColor, color, rows, cols);return image;}private static void dfs(int[][] image, int r, int c, int originalColor, int color, int rows, int cols) {if (image[r][c] == originalColor) {image[r][c] = color;if (r >= 1) dfs(image, r - 1, c, originalColor, color, rows, cols);if (r + 1 < rows) dfs(image, r + 1, c, originalColor, color, rows, cols);if (c >= 1) dfs(image, r, c - 1, originalColor, color, rows, cols);if (c + 1 < cols) dfs(image, r, c + 1, originalColor, color, rows, cols);}return;}
private static void dfs(int[][] image, int r, int c, int originalColor, int color, int rows, int cols) {if (image[r][c] == originalColor) {image[r][c] = color;if (r >= 1) dfs(image, r - 1, c, originalColor, color, rows, cols);if (r + 1 < rows) dfs(image, r + 1, c, originalColor, color, rows, cols);if (c >= 1) dfs(image, r, c - 1, originalColor, color, rows, cols);if (c + 1 < cols) dfs(image, r, c + 1, originalColor, color, rows, cols);}return;}
update color
0 / 2
After changing that pixel's color, the algorithm will continue to explore the connected pixels of that pixel. Whenever it encounters a pixel that is not the same color as the starting pixel, it will return immediately and backtrack to the previous pixel on the call stack, which will then continue to explore its remaining connected pixels.
public static int[][] floodFill(int[][] image, int sr, int sc, int color) {int rows = image.length;int cols = image[0].length;int originalColor = image[sr][sc];if (originalColor == color) {return image;}dfs(image, sr, sc, originalColor, color, rows, cols);return image;}private static void dfs(int[][] image, int r, int c, int originalColor, int color, int rows, int cols) {if (image[r][c] == originalColor) {image[r][c] = color;if (r >= 1) dfs(image, r - 1, c, originalColor, color, rows, cols);if (r + 1 < rows) dfs(image, r + 1, c, originalColor, color, rows, cols);if (c >= 1) dfs(image, r, c - 1, originalColor, color, rows, cols);if (c + 1 < cols) dfs(image, r, c + 1, originalColor, color, rows, cols);}return;}
private static void dfs(int[][] image, int r, int c, int originalColor, int color, int rows, int cols) {if (image[r][c] == originalColor) {image[r][c] = color;if (r >= 1) dfs(image, r - 1, c, originalColor, color, rows, cols);if (r + 1 < rows) dfs(image, r + 1, c, originalColor, color, rows, cols);if (c >= 1) dfs(image, r, c - 1, originalColor, color, rows, cols);if (c + 1 < cols) dfs(image, r, c + 1, originalColor, color, rows, cols);}return;}
private static void dfs(int[][] image, int r, int c, int originalColor, int color, int rows, int cols) {if (image[r][c] == originalColor) {image[r][c] = color;if (r >= 1) dfs(image, r - 1, c, originalColor, color, rows, cols);if (r + 1 < rows) dfs(image, r + 1, c, originalColor, color, rows, cols);if (c >= 1) dfs(image, r, c - 1, originalColor, color, rows, cols);if (c + 1 < cols) dfs(image, r, c + 1, originalColor, color, rows, cols);}return;}
private static void dfs(int[][] image, int r, int c, int originalColor, int color, int rows, int cols) {if (image[r][c] == originalColor) {image[r][c] = color;if (r >= 1) dfs(image, r - 1, c, originalColor, color, rows, cols);if (r + 1 < rows) dfs(image, r + 1, c, originalColor, color, rows, cols);if (c >= 1) dfs(image, r, c - 1, originalColor, color, rows, cols);if (c + 1 < cols) dfs(image, r, c + 1, originalColor, color, rows, cols);}return;}
recursive call
0 / 6
The algorithm will continue to explore the connected pixels of the starting pixel until it has explored all connected pixels of the start pixel.
Animated Solution
public static int[][] floodFill(int[][] image, int sr, int sc, int color) {int rows = image.length;int cols = image[0].length;int originalColor = image[sr][sc];if (originalColor == color) {return image;}dfs(image, sr, sc, originalColor, color, rows, cols);return image;}private static void dfs(int[][] image, int r, int c, int originalColor, int color, int rows, int cols) {if (image[r][c] == originalColor) {image[r][c] = color;if (r >= 1) dfs(image, r - 1, c, originalColor, color, rows, cols);if (r + 1 < rows) dfs(image, r + 1, c, originalColor, color, rows, cols);if (c >= 1) dfs(image, r, c - 1, originalColor, color, rows, cols);if (c + 1 < cols) dfs(image, r, c + 1, originalColor, color, rows, cols);}return;}
flood fill
0 / 39
Complexity Analysis
For this problem, let m be the number of rows and n be the number of columns in the grid.
What is the time complexity of this solution?
O(log m * n)
O(4ⁿ)
O(V + E)
O(m * n)