Log inSign up
easyLeetCodeNot Started

Flood Fill

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value. You are given integers sr, sc, and color. Perform a flood fill on the image starting from the pixel image[sr][sc].

Graph
Solve on LeetCode
Lesson

Problem Statement

### Problem Statement

An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.

You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].

To perform a flood fill: 1. Begin with the starting pixel image[sr][sc] and its original color initialColor. 2. Change the color of the starting pixel to color. 3. Perform the same process for all 4-directionally adjacent pixels (up, down, left, right) that share the same original color initialColor. 4. Keep repeating this process recursively or iteratively until no more adjacent pixels have the original color.

Return the modified image after performing the flood fill.

---

### Examples

Example 1: ``text 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 color 1) are colored with the new color 2. Note the bottom right pixel is not colored 2, because it is not 4-directionally connected to the starting pixel.

Example 2: ``text 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, so no changes are made.

---

### Constraints - m == image.length - n == image[i].length - 1 <= m, n <= 50 - 0 <= image[i][j], color < 2^16 - 0 <= sr < m - 0 <= sc < n

Constraints:

  • 1 <= m, n <= 50
  • 0 <= image[i][j], color < 216
  • 0 <= sr < m
  • 0 <= sc < n

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Recognize implicit graphs on 2D matrices with directional offsets.
  • Prevent infinite loops when the target color equals the original color.
  • Implement both iterative Queue BFS and in-place Recursive DFS.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • 2D grid multi-directional spread or coloring
  • Connected components with matching pixel values
  • Paint bucket tool simulation

Algorithmic Decision Tree:

  • If starting color == target color -> return image immediately.
  • Traverse 4 directions using direction arrays dr = {-1, 1, 0, 0}, dc = {0, 0, -1, 1}.
  • Mutate cell to new color before recursing.

Connected Patterns:

Number of IslandsMax Area of IslandSurrounded Regions

1. Iterative BFS with Explicit Queue

Intuition

Starting from (sr, sc), push coordinates into a queue. Dequeue cell by cell, recolor, and enqueue all 4-directional neighbors that match the original color.

Algorithm

  1. Record originalColor = image[sr][sc].
  2. If originalColor == color, return image.
  3. Initialize queue of pairs and push (sr, sc).
  4. Set image[sr][sc] = color.
  5. Define directions: [(-1, 0), (1, 0), (0, -1), (0, 1)].
  6. While queue is not empty:
  7. Pop (r, c) from queue.
  8. For each (dr, dc) in directions:
  9. nr = r + dr, nc = c + dc.
  10. If 0 <= nr < m and 0 <= nc < n and image[nr][nc] == originalColor:
  11. image[nr][nc] = color.
  12. Push (nr, nc) to queue.
  13. Return image.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5class Solution {
6public:
7 std::vector<std::vector<int>> floodFill(std::vector<std::vector<int>>& image, int sr, int sc, int color) {
8 int originalColor = image[sr][sc];
9 if (originalColor == color) return image;
10
11 int m = image.size();
12 int n = image[0].size();
13 std::queue<std::pair<int, int>> q;
14
15 image[sr][sc] = color;
16 q.push({sr, sc});
17
18 int dr[] = {-1, 1, 0, 0};
19 int dc[] = {0, 0, -1, 1};
20
21 while (!q.empty()) {
22 auto [r, c] = q.front();
23 q.pop();
24
25 for (int i = 0; i < 4; ++i) {
26 int nr = r + dr[i];
27 int nc = c + dc[i];
28 if (nr >= 0 && nr < m && nc >= 0 && nc < n && image[nr][nc] == originalColor) {
29 image[nr][nc] = color;
30 q.push({nr, nc});
31 }
32 }
33 }
34 return image;
35 }
36};
37
38int main() {
39 Solution sol;
40 std::vector<std::vector<int>> image = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
41 auto res = sol.floodFill(image, 1, 1, 2);
42 std::cout << "BFS Flood Fill result:\n";
43 for (const auto& row : res) {
44 for (int v : row) std::cout << v << " ";
45 std::cout << "\n";
46 }
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(m * n)

2. DFS with Visited Matrix

Intuition

Maintain an explicit boolean visited matrix to record visited pixels while recursing along 4 directions.

Algorithm

  1. Initialize visited matrix of dimensions m x n to false.
  2. Record originalColor = image[sr][sc].
  3. Define dfs(r, c):
  4. If r < 0 or r >= m or c < 0 or c >= n or visited[r][c] or image[r][c] != originalColor, return.
  5. visited[r][c] = true.
  6. image[r][c] = color.
  7. dfs(r - 1, c), dfs(r + 1, c), dfs(r, c - 1), dfs(r, c + 1).
  8. Call dfs(sr, sc) and return image.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5 void dfs(std::vector<std::vector<int>>& image, int r, int c, int originalColor, int color, std::vector<std::vector<bool>>& visited) {
6 int m = image.size();
7 int n = image[0].size();
8 if (r < 0 || r >= m || c < 0 || c >= n || visited[r][c] || image[r][c] != originalColor) {
9 return;
10 }
11
12 visited[r][c] = true;
13 image[r][c] = color;
14
15 dfs(image, r - 1, c, originalColor, color, visited);
16 dfs(image, r + 1, c, originalColor, color, visited);
17 dfs(image, r, c - 1, originalColor, color, visited);
18 dfs(image, r, c + 1, originalColor, color, visited);
19 }
20public:
21 std::vector<std::vector<int>> floodFill(std::vector<std::vector<int>>& image, int sr, int sc, int color) {
22 int m = image.size();
23 int n = image[0].size();
24 std::vector<std::vector<bool>> visited(m, std::vector<bool>(n, false));
25 dfs(image, sr, sc, image[sr][sc], color, visited);
26 return image;
27 }
28};
29
30int main() {
31 Solution sol;
32 std::vector<std::vector<int>> image = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
33 auto res = sol.floodFill(image, 1, 1, 2);
34 std::cout << "DFS with Visited Matrix result:\n";
35 for (const auto& row : res) {
36 for (int v : row) std::cout << v << " ";
37 std::cout << "\n";
38 }
39 return 0;
40}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(m * n)

3. In-Place Recursive DFS with Guard Clause (Canonical)

Intuition

By returning immediately when image[sr][sc] == color, the mutated color itself acts as the visited indicator. No auxiliary visited matrix is required, yielding O(1) auxiliary space (excluding recursion stack).

Algorithm

  1. Record originalColor = image[sr][sc].
  2. If originalColor == color, return image immediately.
  3. Define dfs(r, c):
  4. If r < 0 or r >= m or c < 0 or c >= n or image[r][c] != originalColor, return.
  5. image[r][c] = color.
  6. dfs(r - 1, c), dfs(r + 1, c), dfs(r, c - 1), dfs(r, c + 1).
  7. Call dfs(sr, sc).
  8. Return image.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5 void dfs(std::vector<std::vector<int>>& image, int r, int c, int originalColor, int color) {
6 int m = image.size();
7 int n = image[0].size();
8 if (r < 0 || r >= m || c < 0 || c >= n || image[r][c] != originalColor) {
9 return;
10 }
11
12 image[r][c] = color;
13
14 dfs(image, r - 1, c, originalColor, color);
15 dfs(image, r + 1, c, originalColor, color);
16 dfs(image, r, c - 1, originalColor, color);
17 dfs(image, r, c + 1, originalColor, color);
18 }
19public:
20 std::vector<std::vector<int>> floodFill(std::vector<std::vector<int>>& image, int sr, int sc, int color) {
21 if (image[sr][sc] == color) return image;
22 dfs(image, sr, sc, image[sr][sc], color);
23 return image;
24 }
25};
26
27int main() {
28 Solution sol;
29 std::vector<std::vector<int>> image = {{1, 1, 1}, {1, 1, 0}, {1, 0, 1}};
30 auto res = sol.floodFill(image, 1, 1, 2);
31 std::cout << "Canonical In-Place Flood Fill result:\n";
32 for (const auto& row : res) {
33 for (int v : row) std::cout << v << " ";
34 std::cout << "\n";
35 }
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(m * n)
  • Space complexity: O(m * n)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Iterative Queue BFSO(m * n)O(m * n)FIFO queue coordinates expansion layer by layer.Queue memory footprint
2.DFS with Visited MatrixO(m * n)O(m * n)Explicit boolean visited matrix tracks colored pixels.Matrix allocation
3.In-Place Recursive DFS (Canonical)OptimalO(m * n)O(m * n)Guard clause if image[sr][sc] == color; mutates grid in place.Recursion call-stack depth

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Omitting the image[sr][sc] == color guard clause, causing infinite recursion on identical colors.

Pitfall 2:

Checking bounds after accessing image[nr][nc], leading to IndexOutOfBoundsException.

Pitfall 3:

Checking 8 diagonal directions instead of the 4 orthogonal directions requested by the problem.

Crucial Edge Cases to Validate:

  • Starting pixel already has the target color (image[sr][sc] == color) — Early return guard clause terminates in O(1) time without recursing.
  • 1 x 1 single pixel image — Recolors the single cell and terminates as all 4 neighbors are immediately out of bounds.
  • No adjacent pixels match the starting color — Recolors only the starting cell (sr, sc) and returns.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always point out the identical color edge case first — interviewers specifically watch whether you anticipate this infinite recursion bug.
  2. Clarify whether in-place mutation of the input matrix is acceptable or if a copy is required.
  3. Discuss stack overflow safety: for 50x50 grid (2500 calls), recursion is completely safe; for 1000x1000, BFS is required.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is the guard condition if (image[sr][sc] == color) return image; essential in in-place DFS?

2.What is the maximum recursion depth for Flood Fill on an m x n matrix?

3.What are the 4-directional neighbor offsets from cell (r, c)?

Back to DSA Sheet