Flood Fill
Flood Fill is a easy graphs problem solved with the matrix graphs pattern.
The best approach, dfs, runs in O(m · n) time and O(m · n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from bfs up.
Problem
Starting from pixel (sr, sc), recolour it and every pixel connected to it (up, down, left, right) with the same original colour to color. Return the image.
Examples
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]]- Why
- The bottom-right 1 is not connected to the start.
Example 2
- Input
image = [[0,0],[0,0]], sr = 0, sc = 0, color = 0- Output
unchanged
Constraints
1 <= m, n <= 50- 4-directional connectivity.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| BFS | O(m · n) | O(m · n) |
| DFS | O(m · n) | O(m · n) |
1BFS
O(m · n)O(m · n)Queue the start cell, recolour it, and spread to neighbours that still have the old colour.
- If old == color, return the image.
- BFS; recolour cells when they are enqueued.
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
int old = image[sr][sc];
if (old == color) return image;
int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
Queue<int[]> q = new ArrayDeque<>();
q.add(new int[] { sr, sc });
image[sr][sc] = color;
while (!q.isEmpty()) {
int[] c = q.poll();
for (int[] d : dirs) {
int r = c[0] + d[0], k = c[1] + d[1];
if (r >= 0 && k >= 0 && r < image.length && k < image[0].length && image[r][k] == old) {
image[r][k] = color;
q.add(new int[] { r, k });
}
}
}
return image;
}
}class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
old = image[sr][sc]
if old == color:
return image
dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
q = deque([(sr, sc)])
image[sr][sc] = color
while q:
c = q.popleft()
for d in dirs:
r, k = c[0] + d[0], c[1] + d[1]
if r >= 0 and k >= 0 and r < len(image) and k < len(image[0]) and image[r][k] == old:
image[r][k] = color
q.append((r, k))
return imageclass Solution {
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
int old = image[sr][sc];
if (old == color) return image;
int dirs[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
queue<pair<int, int>> q;
q.push({sr, sc});
image[sr][sc] = color;
while (!q.empty()) {
auto c = q.front();
q.pop();
for (auto& d : dirs) {
int r = c.first + d[0], k = c.second + d[1];
if (r >= 0 && k >= 0 && r < (int)image.size() && k < (int)image[0].size() && image[r][k] == old) {
image[r][k] = color;
q.push({r, k});
}
}
}
return image;
}
};function floodFill(image, sr, sc, color) {
const old = image[sr][sc];
if (old === color) return image;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const q = [[sr, sc]];
let head = 0;
image[sr][sc] = color;
while (head < q.length) {
const c = q[head++];
for (const d of dirs) {
const r = c[0] + d[0], k = c[1] + d[1];
if (r >= 0 && k >= 0 && r < image.length && k < image[0].length && image[r][k] === old) {
image[r][k] = color;
q.push([r, k]);
}
}
}
return image;
}2DFS
O(m · n)O(m · n)Recursion depth in the worst case.Recolour the current cell and recurse into each neighbour that still has the old colour. The new colour works as the visited marker.
- If old == color, return.
- fill(r, c): bounds and colour check; set colour; recurse 4 ways.
class Solution {
public int[][] floodFill(int[][] image, int sr, int sc, int color) {
int old = image[sr][sc];
if (old != color) fill(image, sr, sc, old, color);
return image;
}
private void fill(int[][] img, int r, int c, int old, int color) {
if (r < 0 || c < 0 || r >= img.length || c >= img[0].length || img[r][c] != old) return;
img[r][c] = color;
fill(img, r + 1, c, old, color);
fill(img, r - 1, c, old, color);
fill(img, r, c + 1, old, color);
fill(img, r, c - 1, old, color);
}
}class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
old = image[sr][sc]
if old != color:
self.fill(image, sr, sc, old, color)
return image
def fill(self, img: List[List[int]], r: int, c: int, old: int, color: int) -> None:
if r < 0 or c < 0 or r >= len(img) or c >= len(img[0]) or img[r][c] != old:
return
img[r][c] = color
self.fill(img, r + 1, c, old, color)
self.fill(img, r - 1, c, old, color)
self.fill(img, r, c + 1, old, color)
self.fill(img, r, c - 1, old, color)class Solution {
public:
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
int old = image[sr][sc];
if (old != color) fill(image, sr, sc, old, color);
return image;
}
private:
void fill(vector<vector<int>>& img, int r, int c, int old, int color) {
if (r < 0 || c < 0 || r >= (int)img.size() || c >= (int)img[0].size() || img[r][c] != old) return;
img[r][c] = color;
fill(img, r + 1, c, old, color);
fill(img, r - 1, c, old, color);
fill(img, r, c + 1, old, color);
fill(img, r, c - 1, old, color);
}
};function floodFill(image, sr, sc, color) {
const old = image[sr][sc];
if (old !== color) fill(image, sr, sc, old, color);
return image;
}
function fill(img, r, c, old, color) {
if (r < 0 || c < 0 || r >= img.length || c >= img[0].length || img[r][c] !== old) return;
img[r][c] = color;
fill(img, r + 1, c, old, color);
fill(img, r - 1, c, old, color);
fill(img, r, c + 1, old, color);
fill(img, r, c - 1, old, color);
}Edge cases to test
- New colour equals the old colour (without a check, the fill loops forever)
Hints
Hint 1
A grid is a graph: each cell is a node and its 4 neighbours are its edges.
FAQ
What is the best time complexity for Flood Fill?
DFS runs in O(m · n) time and O(m · n) extra space.
Which pattern does Flood Fill use?
It is a graphs problem that uses the matrix graphs pattern. Other problems with the same pattern: Maximum Number of Points From Grid Queries, Contain Virus, Number of Distinct Islands.
Is there a brute force solution for Flood Fill?
Yes. BFS takes O(m · n) time and O(m · n) space. Queue the start cell, recolour it, and spread to neighbours that still have the old colour.
Which edge cases should I test for Flood Fill?
New colour equals the old colour (without a check, the fill loops forever).