Learn how to implement the Floodfill algorithm - a powerful graph traversal technique used in image processing, game development, and more.
public static void floodFill(int[][] grid, int row, int col, int newColor, int oldColor) {
if (row < 0 || row >= grid.length || col < 0 || col >= grid[0].length || grid[row][col] != oldColor) {
return;
}
grid[row][col] = newColor;
floodFill(grid, row + 1, col, newColor, oldColor); // Down
floodFill(grid, row - 1, col, newColor, oldColor); // Up
floodFill(grid, row, col + 1, newColor, oldColor); // Right
floodFill(grid, row, col - 1, newColor, oldColor); // Left
}
int[][] grid = {
{1, 1, 1, 1, 1},
{1, 0, 0, 0, 1},
{1, 0, 0, 0, 1},
{1, 1, 1, 1, 1}
};
// Fill starting at [1,1] with color 2
floodFill(grid, 1, 1, 2, grid[1][1]);
System.out.println(Arrays.deepToString(grid));
/* Output:
[[1, 1, 1, 1, 1],
[1, 2, 2, 2, 1],
[1, 2, 2, 2, 1],
[1, 1, 1, 1, 1]]
*/
public static void floodFillBFS(int[][] grid, int row, int col, int newColor) {
int oldColor = grid[row][col];
if (oldColor == newColor) return;
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[]{row, col});
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
int r = cell[0], c = cell[1];
if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] != oldColor) {
continue;
}
grid[r][c] = newColor;
for (int[] dir : directions) {
queue.add(new int[]{r + dir[0], c + dir[1]});
}
}
}
Implement a floodfill algorithm that uses 8-way connectivity (includes diagonals).
function floodFill(grid, row, col, newColor, useEightWay = false, oldColor = grid[row][col]) {
// Check bounds and color match
if (row < 0 || row >= grid.length ||
col < 0 || col >= grid[0].length ||
grid[row][col] !== oldColor) {
return;
}
// Fill current cell
grid[row][col] = newColor;
// Recursively fill neighbors (4-way connectivity)
floodFill(grid, row + 1, col, newColor, useEightWay, oldColor); // Down
floodFill(grid, row - 1, col, newColor, useEightWay, oldColor); // Up
floodFill(grid, row, col + 1, newColor, useEightWay, oldColor); // Right
floodFill(grid, row, col - 1, newColor, useEightWay, oldColor); // Left
// TODO: Add diagonal directions for 8-way connectivity
// if (useEightWay) {
// ...
// }
}
// Create a test grid
const grid1 = [
[1, 1, 1, 1, 1],
[1, 0, 0, 0, 1],
[1, 0, 1, 0, 1],
[1, 0, 0, 0, 1],
[1, 1, 1, 1, 1]
];
// Test with 4-way connectivity
const grid2 = JSON.parse(JSON.stringify(grid1)); // Deep copy
floodFill(grid2, 1, 1, 2, false);
console.log("4-way result:");
console.log(grid2);
// Test with 8-way connectivity
const grid3 = JSON.parse(JSON.stringify(grid1)); // Deep copy
floodFill(grid3, 1, 1, 2, true);
console.log("8-way result:");
console.log(grid3);
After completing this challenge, try these LeetCode problems: