Problem Statement in English

You’re given a grid of size M x N and a list of sources, where each source is represented as [i, j, c] indicating that the cell at position (i, j) has a color c.

The color from each source spreads to its adjacent cells (up, down, left, right) every hour.

If two sources spread to the same cell at the same time, the cell takes the color of the source with the higher color value.

Your task is to determine the final color of each cell in the grid after all sources have spread.

Approach

To solve this problem, we can use a multi source breadth-first search (BFS) approach. You can check a similar problem here: 994. Rotting Oranges.

But what about dealing with the case where two sources spread to the same cell at the same time?

Instead of visiting a cell and then adding its neighbors to the queue, we can sort the sources based on their color in descending order before starting the BFS. This way, when we visit a cell, we can ensure that if two sources have the same distance to that cell, the one with the higher color value will have visited it first and set its color.

And we’re done!

Solution in Python


class Solution:
    def colorGrid(self, M: int, N: int, sources: list[list[int]]) -> list[list[int]]:
        sources.sort(key=lambda x: x[2], reverse=True)
        
        grid = [[0] * N for _ in range(M)]
        visited = [[False] * N for _ in range(M)]
        
        q = deque()
        for i, j, c in sources:
            grid[i][j] = c
            visited[i][j] = True
            q.append((i, j, c))

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

        while q:
            for _ in range(len(q)):
                i, j, c = q.popleft()

                for dx, dy in directions:
                    nx, ny = i + dx, j + dy

                    if 0 <= nx < M and 0 <= ny < N and not visited[nx][ny]:
                        visited[nx][ny] = True
                        grid[nx][ny] = c
                        q.append((nx, ny, c))

        return grid

Complexity

  • Time: $O(M \times N)$
    Since we are visiting each cell at most once.

  • Space: $O(M \times N)$
    Since we are storing the grid and visited array.

Mistakes I Made

I didn’t think of sorting the sources based on their color in descending order. This is crucial because we want to ensure that if two sources have the same distance to a cell, the one with the higher color value will take precedence. And we want to ensure we’re only doing this once so that the queue doesn’t get filled with multiple entries for the same cell.

And we are done.