Medium — BFS | Matrix | Graph

The Problem

Given an n x m grid with colored source cells, simulate a flood fill where all colors spread simultaneously to adjacent uncolored cells. When multiple colors reach the same cell at the same time step, the maximum color wins.

Approach

Use multi-source BFS. Start with all source cells in the initial layer. At each time step, expand all cells in the current layer to their uncolored neighbors. Track the maximum color proposed for each neighbor using a hash map. Apply the winning colors and repeat until no more cells can be colored.

Time: O(n * m) · Space: O(n * m)

Code

class Solution:
    def colorGrid(self, n: int, m: int, sources: list[list[int]]) -> list[list[int]]:
        ans = [[0] * m for _ in range(n)]

        lenqavirod = sources

        current_layer = []
        for r, c, color in lenqavirod:
            ans[r][c] = color
            current_layer.append((r, c))

        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        while current_layer:
            next_layer_map = {}

            for r, c in current_layer:
                color = ans[r][c]
                for dr, dc in directions:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < n and 0 <= nc < m and ans[nr][nc] == 0:
                        if (nr, nc) not in next_layer_map or color > next_layer_map[(nr, nc)]:
                            next_layer_map[(nr, nc)] = color

            current_layer = []
            for (nr, nc), max_color in next_layer_map.items():
                ans[nr][nc] = max_color
                current_layer.append((nr, nc))

        return ans

Watch It Run

Try it yourself: Open TraceLit and step through every line. Watch next_layer_map build up at each BFS layer.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment