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.

Description Hints 4 Solution Video 16:14

3905. Multi Source Flood Fill

Medium56.3% acceptance

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] = [r_i, c_i, color_i] indicates that the cell (r_i, c_i) is initially colored with color_i. 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 <= 10⁵
1 <= n * m <= 10⁵
1 <= sources.length <= n * m
sources[i] = [r_i, c_i, color_i]
0 <= r_i <= n - 1
0 <= c_i <= m - 1
1 <= color_i <= 10⁶
All (r_i, c_i) in sources are distinct.

Topics

Hints open one at a time

Hint 1

Multi-source BFS

Hint 2

Initialize a queue with all colored cells

Hint 3

Spread colors level by level to adjacent cells in 4 directions

Hint 4

If multiple colors reach the same cell at the same time, assign the maximum color value

16:14

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def colorGrid(self, n: int, m: int, sources: list[list[int]]) -> list[list[int]]:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

3
3
[[0,0,1],[2,2,2]]

Input

3
3
[[0,1,3],[1,1,5]]

Input

2
2
[[1,1,5]]

Your code is saved on this device.Solution