Multi Source Flood Fill solution and explanation
7 more videos on this problem
Multi Source Flood Fill | Leetcode 3905Techdose · 16:14 · 488 views
Leetcode 3905 | Multi Source Flood Fill | Leetcode weekly contest 498CodeWithMeGuys · 10:29 · 268 views
Multi Source Flood Fill | LeetCode 3905 | Weekly Contest 498 | Java Code | Developer CoderDeveloper Coder · 22:06 · 201 views
Multi Source Flood Fill | Leetcode contest 498 | Leetcode 3905 | MUST do BFS | MAANG DSA | contestCode Thoughts · 9:17 · 97 views
3905. Multi Source Flood Fill |Leetcode Weekly 498 Contest solution Easiest Explanation with Dry RunBEASTCODES · 21:12 · 83 views
LeetCode 3905 | Multi Source Flood Fill 🔥 BFS Intuition + Java CodeDev Den · 14:52 · 65 views
LeetCode 3905: Multi Source Flood Fill | Multi-Source BFS | Weekly Contest 498CodingHelp · 13:27 · 20 views
Multi Source Flood Fill | #leetcode #weeklycontest #498 | #3905UMANG AGRAWAL · 16:34 · 16 views
The problem
You are given two integers n and m representing the number of rows and columns of a grid, respectively.
You are also given a 2D integer array sources, where sources[i] = [ri, ci, colori] indicates that the cell (ri, ci) is initially colored with colori. All other cells are initially uncolored and represented as 0.
At each time step, every currently colored cell spreads its color to all adjacent uncolored cells in the four directions: up, down, left, and right. All spreads happen simultaneously.
If multiple colors reach the same uncolored cell at the same time step, the cell takes the color with the maximum value.
The process continues until no more cells can be colored.
Return a 2D integer array representing the final state of the grid, where each cell contains its final color.
Example 1:
Input: n = 3, m = 3, sources = [[0,0,1],[2,2,2]]
Output: [[1,1,2],[1,2,2],[2,2,2]]
Explanation:
The grid at each time step is as follows:
At time step 2, cells (0, 2), (1, 1), and (2, 0) are reached by both colors, so they are assigned color 2 as it has the maximum value among them.
Example 2:
Input: n = 3, m = 3, sources = [[0,1,3],[1,1,5]]
Output: [[3,3,3],[5,5,5],[5,5,5]]
Explanation:
The grid at each time step is as follows:
Example 3:
Input: n = 2, m = 2, sources = [[1,1,5]]
Output: [[5,5],[5,5]]
Explanation:
The grid at each time step is as follows:
Since there is only one source, all cells are assigned the same color.
Constraints:
1 <= n, m <= 1051 <= n * m <= 1051 <= sources.length <= n * msources[i] = [ri, ci, colori]0 <= ri <= n - 10 <= ci <= m - 11 <= colori <= 106- All
(ri, ci)insourcesare distinct.
Approach overview
Problem Overview: You are given a grid where multiple starting cells act as sources of a flood fill. The fill spreads to neighboring cells step by step until all reachable cells are processed. The challenge is handling several starting points efficiently while traversing the matrix.
Approach 1: Run Flood Fill from Each Source Separately (Brute Force) (Time: O(k * m * n), Space: O(m * n))
A straightforward idea is to perform a standard flood fill (DFS or BFS) starting from every source cell independently. For each source, you traverse the matrix and update reachable cells. If there are k sources and the grid size is m × n, the traversal may repeat large portions of the grid for each source. This leads to O(k * m * n) time in the worst case. While simple to implement, it wastes work because neighboring sources may repeatedly explore the same cells.
Approach 2: Multi-Source Breadth-First Search (Optimal) (Time: O(m * n), Space: O(m * n))
The efficient solution pushes all source cells into the queue at once and runs a single BFS traversal. Each step pops a cell from the queue and spreads the flood to its valid neighbors (up, down, left, right). Because BFS processes nodes layer by layer, the flood expands simultaneously from every source. Each cell enters the queue at most once, which guarantees O(m * n) time. A visited matrix or in-place marking prevents revisiting cells.
This pattern is known as multi-source BFS and appears frequently in grid problems such as distance propagation, infection spread, or shortest path in unweighted matrices. By initializing the queue with all sources, you eliminate redundant traversals and naturally compute the earliest time or step each cell becomes filled.
Implementation details are straightforward. Iterate through the grid, detect all starting cells, and push them into a queue. Then repeatedly pop from the queue, inspect the four neighbors, check bounds, and enqueue unvisited cells after marking them filled. This traversal style relies heavily on concepts from breadth-first search and grid traversal patterns commonly used with matrix problems.
Recommended for interviews: Interviewers expect the multi-source BFS approach. The brute force method demonstrates that you understand flood fill mechanics, but the optimal solution shows you recognize overlapping work and know how to coordinate multiple starting points using a queue. Problems involving grids and spreading processes almost always reduce to this BFS pattern with a queue and directional traversal over a 2D array.
Solution
We can use multi-source BFS to simulate this process.
Define a queue q to store the cells that are currently spreading their color. Initially, add all source cells to the queue and set their colors in the answer array ans.
In each iteration, we use a hash table vis to record the cells visited at the current time step and the maximum color value for each cell. For each cell in the queue, we try to spread its color to the four adjacent directions (up, down, left, right). If a neighboring cell is uncolored, we add it to vis and update its color to be the maximum of the current cell's color and any existing color in vis.
After processing all cells in the current queue, we clear the queue and add the cells from vis to the queue, updating their colors in the answer array ans accordingly.
We repeat this process until the queue is empty, meaning no more cells can be colored.
The time complexity is O(n times m) and the space complexity is O(n times m), where n and m are the number of rows and columns in the grid, respectively.
class Solution:
def colorGrid(self, n: int, m: int, sources: list[list[int]]) -> list[list[int]]:
ans = [[0] * m for _ in range(n)]
q = sources
dirs = (-1, 0, 1, 0, -1)
for r, c, color in q:
ans[r][c] = color
while q:
vis = defaultdict(int)
for r, c, color in q:
for a, b in pairwise(dirs):
x, y = r + a, c + b
if not 0 <= x < n or not 0 <= y < m or ans[x][y]:
continue
vis[(x, y)] = max(vis[(x, y)], color)
q.clear()
for (x, y), color in vis.items():
q.append((x, y, color))
ans[x][y] = color
return ansclass Solution {
public int[][] colorGrid(int n, int m, int[][] sources) {
int[][] ans = new int[n][m];
List<int[]> q = new ArrayList<>();
int[] dirs = {-1, 0, 1, 0, -1};
for (int[] s : sources) {
ans[s[0]][s[1]] = s[2];
q.add(new int[] {s[0], s[1], s[2]});
}
while (!q.isEmpty()) {
Map<Long, Integer> vis = new HashMap<>();
for (int[] curr : q) {
int r = curr[0], c = curr[1], color = curr[2];
for (int i = 0; i < 4; i++) {
int x = r + dirs[i], y = c + dirs[i + 1];
if (x >= 0 && x < n && y >= 0 && y < m && ans[x][y] == 0) {
long key = (long) x * m + y;
vis.put(key, Math.max(vis.getOrDefault(key, 0), color));
}
}
}
q.clear();
for (Map.Entry<Long, Integer> entry : vis.entrySet()) {
int x = (int) (entry.getKey() / m);
int y = (int) (entry.getKey() % m);
int color = entry.getValue();
ans[x][y] = color;
q.add(new int[] {x, y, color});
}
}
return ans;
}
}class Solution {
public:
vector<vector<int>> colorGrid(int n, int m, vector<vector<int>>& sources) {
vector<vector<int>> ans(n, vector<int>(m, 0));
vector<array<int, 3>> q;
int dirs[] = {-1, 0, 1, 0, -1};
for (auto& s : sources) {
ans[s[0]][s[1]] = s[2];
q.push_back({s[0], s[1], s[2]});
}
while (!q.empty()) {
unordered_map<long long, int> vis;
for (auto& curr : q) {
int r = curr[0], c = curr[1], color = curr[2];
for (int i = 0; i < 4; i++) {
int x = r + dirs[i], y = c + dirs[i + 1];
if (x >= 0 && x < n && y >= 0 && y < m && ans[x][y] == 0) {
long long key = (long long) x * m + y;
if (color > vis[key]) {
vis[key] = color;
}
}
}
}
q.clear();
for (auto const& [key, color] : vis) {
int x = key / m;
int y = key % m;
ans[x][y] = color;
q.push_back({x, y, color});
}
}
return ans;
}
};function colorGrid(n: number, m: number, sources: number[][]): number[][] {
const ans: number[][] = Array.from({ length: n }, () => Array(m).fill(0));
let q: number[][] = [...sources.map(s => [...s])];
const dirs = [-1, 0, 1, 0, -1];
for (const [r, c, color] of q) {
ans[r][c] = color;
}
while (q.length > 0) {
const vis: Map<string, number> = new Map();
for (const [r, c, color] of q) {
for (let i = 0; i < 4; i++) {
const x = r + dirs[i],
y = c + dirs[i + 1];
if (x >= 0 && x < n && y >= 0 && y < m && ans[x][y] === 0) {
const key = `${x},${y}`;
vis.set(key, Math.max(vis.get(key) || 0, color));
}
}
}
q = [];
for (const [key, color] of vis.entries()) {
const [x, y] = key.split(',').map(Number);
ans[x][y] = color;
q.push([x, y, color]);
}
}
return ans;
}func colorGrid(n int, m int, sources [][]int) [][]int {
ans := make([][]int, n)
for i := range ans {
ans[i] = make([]int, m)
}
q := make([][]int, len(sources))
copy(q, sources)
dirs := []int{-1, 0, 1, 0, -1}
for _, s := range q {
ans[s[0]][s[1]] = s[2]
}
for len(q) > 0 {
vis := make(map[[2]int]int)
for _, curr := range q {
r, c, color := curr[0], curr[1], curr[2]
for i := 0; i < 4; i++ {
x, y := r+dirs[i], c+dirs[i+1]
if x >= 0 && x < n && y >= 0 && y < m && ans[x][y] == 0 {
if color > vis[[2]int{x, y}] {
vis[[2]int{x, y}] = color
}
}
}
}
q = nil
for pos, color := range vis {
ans[pos[0]][pos[1]] = color
q = append(q, []int{pos[0], pos[1], color})
}
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Run Flood Fill from Each Source (DFS/BFS) | O(k * m * n) | O(m * n) | Useful for understanding the flood fill process or when the number of sources is extremely small. |
| Multi-Source BFS | O(m * n) | O(m * n) | Best general solution for matrix spread problems with multiple starting points. |
Frequently asked questions
Is Multi Source Flood Fill easy or hard?
Multi Source Flood Fill is generally considered a medium-level problem. The challenge is recognizing that multiple starting points should be processed together using BFS rather than running flood fill repeatedly from each source.
Multi Source Flood Fill Python/Java solution
Both Python and Java implementations follow the same pattern: collect all source coordinates, push them into a queue, and perform BFS using four-directional movement. Each iteration pops a cell, checks neighbors, and enqueues valid unvisited cells until the queue becomes empty.
How to solve Multi Source Flood Fill in O(n)?
Treat all source cells as the first layer of a BFS. Insert them into a queue and process neighbors in four directions while marking visited cells. Since each matrix cell is pushed and popped at most once, the traversal finishes in O(m*n) time.
What is the best approach for Multi Source Flood Fill?
The optimal approach is multi-source Breadth-First Search (BFS). Push all source cells into a queue at the start, then expand to neighboring cells layer by layer. Each cell is processed once, giving O(m*n) time complexity and O(m*n) space for the queue and visited tracking.
Is Multi Source Flood Fill asked at Google/Amazon/Meta?
Matrix BFS problems and multi-source BFS patterns appear frequently in interviews at companies like Amazon, Google, and Meta. Variations include problems like Rotting Oranges, Walls and Gates, and distance-to-nearest-source questions.
What data structure is used in Multi Source Flood Fill?
The main data structure is a queue used for BFS traversal. A visited matrix or in-place grid updates are also used to prevent processing the same cell multiple times while expanding the flood.
What is the time complexity of Multi Source Flood Fill?
The optimal multi-source BFS solution runs in O(m*n) time where m and n are the grid dimensions. Each cell is visited at most once and each edge (neighbor relationship) is checked a constant number of times.