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(ri, ci) in sources are distinct.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.
Solutions for this problem are being prepared.
Try solving it yourself| 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. |
Practice Multi Source Flood Fill with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor