Flood Fill solution and explanation
Google
9 more videos on this problem
G-9. Flood Fill Algorithm | C++ | Javatake U forward · 20:34 · 465K views
LeetCode 733. Flood Fill (Algorithm Explained)Nick White · 10:03 · 67K views
Flood Fill | Leetcode #733Techdose · 10:33 · 58K views
Leetcode 733. Flood Fill - PythonHelmyCodeCamp · 6:56 · 9K views
14. Flood Fill Algo using BFS | LeetCode 733 | Intuition with Easy C++, JAVA Code | MUST DO Algos!Keerti Purswani · 14:56 · 5K views
Flood Fill LeetCode | Flood Fill Java Solution | LeetCode 733 | Programming TutorialsProgramming Tutorials · 9:09 · 3K views
Flood Fill | Leetcode 733 | C++Leetcoding · 12:40 · 709 views
LeetCode 733 - Flood Fill - C++iamdriy · 12:44 · 444 views
733. Flood Fill || LeetCode || C++ || Graph Series.Code with Sky · 16:25 · 377 views
LeetCode 733. Flood Fill | Island Matrix Part 1 | C#Base Case · 3:41 · 280 views
The problem
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:
- Begin with the starting pixel and change its color to
color. - Perform the same process for each pixel that is directly adjacent (pixels that share a side with the original pixel, either horizontally or vertically) and shares the same color as the starting pixel.
- Keep repeating this process by checking neighboring pixels of the updated pixels and modifying their color if it matches the original color of the starting pixel.
- The process stops when there are no more adjacent pixels of the original color to update.
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 < n
Approach overview
Problem Overview: You are given a 2D image where each cell represents a pixel color. Starting from a specific pixel (sr, sc), change its color and all 4-directionally connected pixels with the same original color to a new color. The task is essentially traversing a connected component in a grid.
Approach 1: Recursive Depth-First Search (DFS) (Time: O(m*n), Space: O(m*n))
This approach treats the grid as a graph and performs a recursive DFS from the starting cell. First store the original color at (sr, sc). If the new color is the same as the original, return immediately to avoid infinite recursion. Otherwise, recursively explore the four directions (up, down, left, right). Whenever a neighboring cell has the same original color, update it and continue the DFS. Each cell is visited at most once, giving O(m*n) time for an image of size m x n. The recursion stack can grow up to the size of the connected region, resulting in O(m*n) space in the worst case. This method is simple and maps naturally to problems involving Depth-First Search on a matrix.
Approach 2: Iterative Breadth-First Search (BFS) (Time: O(m*n), Space: O(m*n))
The BFS approach performs the same region traversal but uses a queue instead of recursion. Start by pushing the initial pixel into a queue and recolor it. While the queue is not empty, pop a cell and examine its four neighbors. If a neighbor lies within bounds and has the original color, recolor it and push it into the queue. BFS expands level by level across the connected component, ensuring every valid pixel is processed exactly once. Time complexity remains O(m*n) because each pixel is enqueued and processed at most once. Space complexity is also O(m*n) due to the queue in the worst case when the entire grid belongs to the same region. This approach is useful when recursion depth might be large and iterative control is preferred, especially in problems involving Breadth-First Search over an array-backed grid.
Recommended for interviews: The recursive DFS solution is the most common answer because it is concise and clearly demonstrates understanding of grid traversal. Interviewers typically expect you to recognize the problem as a connected component search. Mentioning both DFS and BFS shows strong fundamentals: DFS demonstrates recursion and graph traversal intuition, while BFS shows awareness of iterative alternatives and stack depth limitations.
Approach 1: Recursive Depth-First Search (DFS) Approach
This 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).
def flood_fill(image, sr, sc, new_color):
original_color = image[sr][sc]
if original_color == new_color: return image
def dfs(r, c):
if r < 0 or r >= len(image) or c < 0 or c >= len(image[0]) or image[r][c] != original_color:
return
image[r][c] = new_color
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
dfs(sr, sc)
return imageclass Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
int originalColor = image[sr][sc];
if (originalColor != newColor) {
dfs(image, sr, sc, originalColor, newColor);
}
return image;
}
private void dfs(int[][] image, int r, int c, int originalColor, int newColor) {
if (r < 0 || r >= image.length || c < 0 || c >= image[0].length || image[r][c] != originalColor)
return;
image[r][c] = newColor;
dfs(image, r + 1, c, originalColor, newColor);
dfs(image, r - 1, c, originalColor, newColor);
dfs(image, r, c + 1, originalColor, newColor);
dfs(image, r, c - 1, originalColor, newColor);
}
}#include <vector>
using namespace std;
void dfs(vector<vector<int>>& image, int r, int c, int originalColor, int newColor) {
if (r < 0 || r >= image.size() || c < 0 || c >= image[0].size() || image[r][c] != originalColor)
return;
image[r][c] = newColor;
dfs(image, r + 1, c, originalColor, newColor);
dfs(image, r - 1, c, originalColor, newColor);
dfs(image, r, c + 1, originalColor, newColor);
dfs(image, r, c - 1, originalColor, newColor);
}
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
int originalColor = image[sr][sc];
if (originalColor != newColor) {
dfs(image, sr, sc, originalColor, newColor);
}
return image;
}function floodFill(image, sr, sc, newColor) {
const originalColor = image[sr][sc];
if (originalColor !== newColor) {
dfs(image, sr, sc, originalColor, newColor);
}
return image;
function dfs(image, r, c, originalColor, newColor) {
if (r < 0 || r >= image.length || c < 0 || c >= image[0].length || image[r][c] !== originalColor) return;
image[r][c] = newColor;
dfs(image, r + 1, c, originalColor, newColor);
dfs(image, r - 1, c, originalColor, newColor);
dfs(image, r, c + 1, originalColor, newColor);
dfs(image, r, c - 1, originalColor, newColor);
}
}#include <stdio.h>
void dfs(int** image, int m, int n, int r, int c, int originalColor, int newColor) {
if (r < 0 || r >= m || c < 0 || c >= n || image[r][c] != originalColor) return;
image[r][c] = newColor;
dfs(image, m, n, r + 1, c, originalColor, newColor);
dfs(image, m, n, r - 1, c, originalColor, newColor);
dfs(image, m, n, r, c + 1, originalColor, newColor);
dfs(image, m, n, r, c - 1, originalColor, newColor);
}
int** floodFill(int** image, int m, int n, int sr, int sc, int color, int* returnSize, int** returnColumnSizes) {
int originalColor = image[sr][sc];
if (originalColor != color) {
dfs(image, m, n, sr, sc, originalColor, color);
}
return image;
}public class Solution {
public int[][] FloodFill(int[][] image, int sr, int sc, int newColor) {
int originalColor = image[sr][sc];
if(originalColor != newColor) {
DFS(image, sr, sc, originalColor, newColor);
}
return image;
}
private void DFS(int[][] image, int r, int c, int originalColor, int newColor) {
if (r < 0 || r >= image.Length || c < 0 || c >= image[0].Length || image[r][c] != originalColor) return;
image[r][c] = newColor;
DFS(image, r + 1, c, originalColor, newColor);
DFS(image, r - 1, c, originalColor, newColor);
DFS(image, r, c + 1, originalColor, newColor);
DFS(image, r, c - 1, originalColor, newColor);
}
}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.
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.
Approach 2: Iterative Breadth-First Search (BFS) Approach
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.
from collections import deque
def flood_fill(image, sr, sc, new_color):
original_color = image[sr][sc]
if original_color == new_color:
return image
rows, cols = len(image), len(image[0])
queue = deque([(sr, sc)])
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
while queue:
r, c = queue.popleft()
if image[r][c] == original_color:
image[r][c] = new_color
for dr, dc in directions:
rr, cc = r + dr, c + dc
if 0 <= rr < rows and 0 <= cc < cols and image[rr][cc] == original_color:
queue.append((rr, cc))
return imageimport java.util.LinkedList;
import java.util.Queue;
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
int originalColor = image[sr][sc];
if (originalColor == newColor) return image;
int rows = image.length;
int cols = image[0].length;
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{sr, sc});
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 (image[r][c] == originalColor) {
image[r][c] = newColor;
for (int[] d : directions) {
int rr = r + d[0], cc = c + d[1];
if (rr >= 0 && rr < rows && cc >= 0 && cc < cols && image[rr][cc] == originalColor) {
queue.offer(new int[]{rr, cc});
}
}
}
}
return image;
}
}#include <vector>
#include <queue>
using namespace std;
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
int originalColor = image[sr][sc];
if (originalColor == newColor) return image;
int rows = image.size();
int cols = image[0].size();
queue<pair<int, int>> q;
q.push({sr, sc});
vector<pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
if (image[r][c] == originalColor) {
image[r][c] = newColor;
for (auto [dr, dc] : directions) {
int rr = r + dr, cc = c + dc;
if (rr >= 0 && rr < rows && cc >= 0 && cc < cols && image[rr][cc] == originalColor) {
q.push({rr, cc});
}
}
}
}
return image;
}function floodFill(image, sr, sc, newColor) {
const originalColor = image[sr][sc];
if (originalColor === newColor) return image;
const rows = image.length;
const cols = image[0].length;
const queue = [[sr, sc]];
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
while (queue.length > 0) {
const [r, c] = queue.shift();
if (image[r][c] === originalColor) {
image[r][c] = newColor;
for (let [dr, dc] of directions) {
const rr = r + dr;
const cc = c + dc;
if (rr >= 0 && rr < rows && cc >= 0 && cc < cols && image[rr][cc] === originalColor) {
queue.push([rr, cc]);
}
}
}
}
return image;
}#include <stdlib.h>
#include <stdbool.h>
void enqueue(int *queue, int *rear, int *r, int *c) {
queue[(*rear)++] = *r;
queue[(*rear)++] = *c;
}
void dequeue(int *queue, int *front, int *r, int *c) {
*r = queue[(*front)++];
*c = queue[(*front)++];
}
bool isEmpty(int front, int rear) {
return front == rear;
}
int** floodFill(int** image, int imageSize, int* imageColSize, int sr, int sc, int newColor, int* returnSize, int** returnColumnSizes) {
int originalColor = image[sr][sc];
if (originalColor == newColor) return image;
int rows = imageSize;
int cols = imageColSize[0];
int queue[rows * cols * 2];
int front = 0, rear = 0;
enqueue(queue, &rear, &sr, &sc);
int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!isEmpty(front, rear)) {
int r, c;
dequeue(queue, &front, &r, &c);
if (image[r][c] == originalColor) {
image[r][c] = newColor;
for (int d = 0; d < 4; ++d) {
int rr = r + directions[d][0];
int cc = c + directions[d][1];
if (rr >= 0 && rr < rows && cc >= 0 && cc < cols && image[rr][cc] == originalColor) {
enqueue(queue, &rear, &rr, &cc);
}
}
}
}
*returnSize = imageSize;
*returnColumnSizes = imageColSize;
return image;
}using System.Collections.Generic;
public class Solution {
public int[][] FloodFill(int[][] image, int sr, int sc, int newColor) {
int originalColor = image[sr][sc];
if (originalColor == newColor) return image;
int rows = image.Length;
int cols = image[0].Length;
Queue<(int, int)> queue = new Queue<(int, int)>();
queue.Enqueue((sr, sc));
int[][] directions = new int[][] { new int[] {1, 0}, new int[] {-1, 0}, new int[] {0, 1}, new int[] {0, -1} };
while (queue.Count > 0) {
var (r, c) = queue.Dequeue();
if (image[r][c] == originalColor) {
image[r][c] = newColor;
foreach (var d in directions) {
int rr = r + d[0], cc = c + d[1];
if (rr >= 0 && rr < rows && cc >= 0 && cc < cols && image[rr][cc] == originalColor) {
queue.Enqueue((rr, cc));
}
}
}
}
return image;
}
}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.
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 3: DFS
We denote the initial pixel's color as oc. If oc is not equal to the target color color, we start a depth-first search from (sr, sc) to change the color of all eligible pixels to the target color.
The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the number of rows and columns of the 2D array image, respectively.
function floodFill(image: number[][], sr: number, sc: number, color: number): number[][] {
const [m, n] = [image.length, image[0].length];
const oc = image[sr][sc];
if (oc === color) {
return image;
}
const dirs = [-1, 0, 1, 0, -1];
const dfs = (i: number, j: number): void => {
image[i][j] = color;
for (let k = 0; k < 4; k++) {
const [x, y] = [i + dirs[k], j + dirs[k + 1]];
if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] === oc) {
dfs(x, y);
}
}
};
dfs(sr, sc);
return image;
}func floodFill(image [][]int, sr int, sc int, color int) [][]int {
m, n := len(image), len(image[0])
oc := image[sr][sc]
if oc == color {
return image
}
dirs := []int{-1, 0, 1, 0, -1}
var dfs func(i, j int)
dfs = func(i, j int) {
image[i][j] = color
for k := 0; k < 4; k++ {
x, y := i+dirs[k], j+dirs[k+1]
if x >= 0 && x < m && y >= 0 && y < n && image[x][y] == oc {
dfs(x, y)
}
}
}
dfs(sr, sc)
return image
}impl Solution {
pub fn flood_fill(mut image: Vec<Vec<i32>>, sr: i32, sc: i32, color: i32) -> Vec<Vec<i32>> {
let m = image.len();
let n = image[0].len();
let sr = sr as usize;
let sc = sc as usize;
let oc = image[sr][sc];
if oc == color {
return image;
}
let dirs = [-1, 0, 1, 0, -1];
fn dfs(
image: &mut Vec<Vec<i32>>,
i: usize,
j: usize,
oc: i32,
color: i32,
m: usize,
n: usize,
dirs: &[i32; 5],
) {
image[i][j] = color;
for k in 0..4 {
let x = i as isize + dirs[k] as isize;
let y = j as isize + dirs[k + 1] as isize;
if x >= 0 && x < m as isize && y >= 0 && y < n as isize {
let x = x as usize;
let y = y as usize;
if image[x][y] == oc {
dfs(image, x, y, oc, color, m, n, dirs);
}
}
}
}
dfs(&mut image, sr, sc, oc, color, m, n, &dirs);
image
}
}Approach 4: BFS
We first check if the initial pixel's color is equal to the target color. If it is, we return the original image directly. Otherwise, we can use the breadth-first search method, starting from (sr, sc), to change the color of all eligible pixels to the target color.
Specifically, we define a queue q and add the initial pixel (sr, sc) to the queue. Then, we continuously take pixels (i, j) from the queue, change their color to the target color, and add the pixels in the four directions (up, down, left, right) that have the same original color as the initial pixel to the queue. When the queue is empty, we have completed the flood fill.
The time complexity is O(m times n), and the space complexity is O(m times n). Here, m and n are the number of rows and columns of the 2D array image, respectively.
function floodFill(image: number[][], sr: number, sc: number, color: number): number[][] {
if (image[sr][sc] === color) {
return image;
}
const oc = image[sr][sc];
image[sr][sc] = color;
const q: [number, number][] = [];
q.push([sr, sc]);
const dirs = [-1, 0, 1, 0, -1];
const [m, n] = [image.length, image[0].length];
while (q.length > 0) {
const [a, b] = q.shift()!;
for (let k = 0; k < 4; ++k) {
const x = a + dirs[k];
const y = b + dirs[k + 1];
if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] === oc) {
q.push([x, y]);
image[x][y] = color;
}
}
}
return image;
}func floodFill(image [][]int, sr int, sc int, color int) [][]int {
if image[sr][sc] == color {
return image
}
oc := image[sr][sc]
q := [][]int{[]int{sr, sc}}
image[sr][sc] = color
dirs := []int{-1, 0, 1, 0, -1}
for len(q) > 0 {
p := q[0]
q = q[1:]
for k := 0; k < 4; k++ {
x, y := p[0]+dirs[k], p[1]+dirs[k+1]
if x >= 0 && x < len(image) && y >= 0 && y < len(image[0]) && image[x][y] == oc {
q = append(q, []int{x, y})
image[x][y] = color
}
}
}
return image
}use std::collections::VecDeque;
impl Solution {
pub fn flood_fill(mut image: Vec<Vec<i32>>, sr: i32, sc: i32, color: i32) -> Vec<Vec<i32>> {
let m = image.len();
let n = image[0].len();
let (sr, sc) = (sr as usize, sc as usize);
if image[sr][sc] == color {
return image;
}
let oc = image[sr][sc];
image[sr][sc] = color;
let mut q = VecDeque::new();
q.push_back((sr, sc));
let dirs = [-1, 0, 1, 0, -1];
while let Some((i, j)) = q.pop_front() {
for k in 0..4 {
let x = i as isize + dirs[k] as isize;
let y = j as isize + dirs[k + 1] as isize;
if x >= 0 && x < m as isize && y >= 0 && y < n as isize {
let (x, y) = (x as usize, y as usize);
if image[x][y] == oc {
q.push_back((x, y));
image[x][y] = color;
}
}
}
}
image
}
}Complexity comparison
| 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). |
| DFS | – |
| BFS | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive DFS | O(m*n) | O(m*n) | Best for concise implementation and typical interview solutions involving recursive grid traversal |
| Iterative BFS | O(m*n) | O(m*n) | Useful when avoiding recursion depth limits or when iterative queue-based traversal is preferred |
Frequently asked questions
Is Flood Fill easy or hard?
Flood Fill is classified as an Easy problem on LeetCode with a relatively high acceptance rate. The challenge mainly involves recognizing it as a grid traversal problem and correctly handling boundaries and repeated visits.
How to solve Flood Fill in O(n)?
Treat the grid as a graph and traverse the connected component using DFS or BFS. Store the original color, then explore four directions from the starting cell and recolor matching neighbors. Each pixel is visited once, resulting in O(m*n) time for a grid with m rows and n columns.
What is the best approach for Flood Fill?
Depth-First Search (DFS) is the most common approach. Starting from the source pixel, recursively visit neighboring cells that share the same original color and update them to the new color. Each cell is processed once, giving O(m*n) time complexity for an m x n image.
What data structure is used in Flood Fill?
Flood Fill uses either the call stack for recursive DFS or a queue for iterative BFS. The image itself is typically represented as a 2D array or matrix, and traversal checks the four directional neighbors of each cell.
What is the time complexity of Flood Fill?
Flood Fill runs in O(m*n) time because every pixel in the grid can be visited at most once during the traversal. Both DFS and BFS implementations have the same complexity since they explore the connected component of the starting pixel.
Flood Fill Python or Java solution approach?
In Python or Java, the solution typically implements recursive DFS that checks boundary conditions and color matches before recursing to neighbors. An alternative BFS version uses a queue to iteratively process pixels level by level.
Is Flood Fill asked at Google, Amazon, or Meta?
Flood Fill and similar grid traversal problems appear in interviews at major companies including Amazon, Google, and Meta. The problem tests understanding of graph traversal, recursion, and matrix boundary handling.