LeetCode 3905 - Multi Source Flood Fill

LeetCode Problem 3905

Difficulty: 🟡 Medium
Topics: Array, Breadth-First Search, Matrix

Solution

Problem Understanding

The problem asks us to simulate a multi-source flood fill on an n x m grid. Each element of the sources array represents a starting point with a specific color, and all other cells start uncolored, represented as 0. At each time step, the currently colored cells spread their color to their four immediate neighbors (up, down, left, right) if the neighboring cell is uncolored. If multiple colors attempt to fill the same cell simultaneously, the maximum color value among them is chosen.

The input consists of integers n and m, specifying the grid size, and a list of sources, where each source is [row, col, color]. The output is the final state of the grid after all possible spreads have occurred.

The constraints indicate that the product of n * m is at most 10^5, meaning the grid can be sparse but large in one dimension. Each color is a positive integer up to 10^6, and all sources are distinct. This ensures there is no initial conflict at the starting cells. Edge cases to consider include having only one source, sources on edges or corners, and multiple sources whose spreads collide.

Approaches

A brute-force approach would simulate the process step by step. At each step, we would iterate over the entire grid and attempt to color neighboring cells. While this would produce the correct result, it is inefficient because iterating over the full grid in each step can lead to O((n * m) * steps) time complexity, which may exceed 10^5 iterations.

The optimal approach uses multi-source BFS. We treat all source cells as starting points and perform a level-order BFS using a queue. At each BFS level, we color uncolored neighbors and resolve conflicts by taking the maximum color when multiple cells attempt to color the same neighbor. Using BFS ensures that all spreads from the current "wave" happen simultaneously. This approach visits each cell exactly once, giving an O(n * m) time complexity.

Algorithm Walkthrough

1. Initialize an n x m grid filled with zeros. This represents uncolored cells.

2. Create a queue and enqueue all sources as tuples (row, col, color).

3. For each source, mark its position in the grid with its color. This is the initial coloring.

4. While the queue is not empty:

5. Dequeue a cell (r, c, color).

6. For each of the four neighbors (nr, nc):

7. If (nr, nc) is within bounds and uncolored, set a temporary mapping for that neighbor to track the maximum color reaching it at this level.

8. After processing all neighbors at this BFS level, update the grid for all newly colored cells using the maximum color computed, and enqueue them with their assigned color.

9. Continue until the queue is empty, at which point all reachable cells have been colored.

Why it works: BFS ensures that spreads happen level by level, simulating simultaneous spread from multiple sources. Using a temporary mapping to take the maximum color at each level guarantees that conflict resolution rules are respected.

Python Solution

from collections import deque

class Solution:
    def colorGrid(self, n: int, m: int, sources: list[list[int]]) -> list[list[int]]:
        grid = [[0] * m for _ in range(n)]
        q = deque()
        
        for r, c, color in sources:
            grid[r][c] = color
            q.append((r, c, color))
        
        directions = [(-1,0), (1,0), (0,-1), (0,1)]
        
        while q:
            level_size = len(q)
            temp = {}
            for _ in range(level_size):
                r, c, color = q.popleft()
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] == 0:
                        if (nr, nc) not in temp:
                            temp[(nr, nc)] = color
                        else:
                            temp[(nr, nc)] = max(temp[(nr, nc)], color)
            for (nr, nc), color in temp.items():
                grid[nr][nc] = color
                q.append((nr, nc, color))
        
        return grid

In the implementation, grid holds the current state of the cells. A queue tracks the BFS wavefront, while temp temporarily stores the maximum color for each cell reached in the current BFS level. This ensures conflicts are resolved according to the maximum color rule before cells are officially updated.

Go Solution

package main

func colorGrid(n int, m int, sources [][]int) [][]int {
    grid := make([][]int, n)
    for i := 0; i < n; i++ {
        grid[i] = make([]int, m)
    }
    
    type cell struct {
        r, c, color int
    }
    
    q := []cell{}
    for _, s := range sources {
        r, c, color := s[0], s[1], s[2]
        grid[r][c] = color
        q = append(q, cell{r, c, color})
    }
    
    directions := [][2]int{{-1,0},{1,0},{0,-1},{0,1}}
    
    for len(q) > 0 {
        levelSize := len(q)
        temp := map[[2]int]int{}
        for i := 0; i < levelSize; i++ {
            cur := q[0]
            q = q[1:]
            for _, d := range directions {
                nr, nc := cur.r + d[0], cur.c + d[1]
                if nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] == 0 {
                    key := [2]int{nr, nc}
                    if val, ok := temp[key]; ok {
                        if cur.color > val {
                            temp[key] = cur.color
                        }
                    } else {
                        temp[key] = cur.color
                    }
                }
            }
        }
        for k, color := range temp {
            r, c := k[0], k[1]
            grid[r][c] = color
            q = append(q, cell{r, c, color})
        }
    }
    
    return grid
}

In Go, slices and maps are used instead of Python lists and dictionaries. The BFS level processing uses a temporary map with [2]int keys to store maximum color values for conflict resolution.

Worked Examples

Example 1: n=3, m=3, sources=[[0,0,1],[2,2,2]]

Complexity Analysis

The BFS ensures linear time in the number of cells, while the temporary map ensures conflict resolution does not require revisiting cells multiple times.

Test Cases

# Provided examples
assert Solution().colorGrid(3,3,[[0,0,1],[2,2,2]]) == [[1,1,2],[1,2,2],[2,2,2]] # conflict resolved
assert Solution().colorGrid(3,3,[[0,1,3],[1,1,5]]) == [[3,3,3],[5,5,5],[5,5,5]] # overlapping spreads
assert Solution().colorGrid(2,2,[[1,1,5]]) == [[5,5],[5,5]] # single source

# Edge cases
assert Solution().colorGrid(1,1,[[0,0,7]]) == [[7]] # smallest grid
assert Solution().colorGrid(2,3,[[0,0,2],[1,2,3]]) == [[2,2,3],[2,3,3]] # rectangular grid
assert Solution().colorGrid(3,3,[[0,0,1],[0,2,2],[2,0,3],[2,2,4]]) == [[1,1,2],[1,4,2],[3,