https://leetcode.com/problems/rotting-oranges

This is graph traversal problem, so here we have a choise: to use dfs or to use bfs. What is asked: minimum number of minutes passed until there is no fresh orange. In graphs it means to find the greatest distance from rotten oranges to any other orange. Usually, if we need to find the distances, we use bfs. So, let me define my variables:

  1. m and n are dimensions of our grid, also we have queue to run our bfs and also we want to count number of fresh oranges: we need this to check in the end if all oranges become rotten or not.
  2. We put all rotten oranges coordinates to our queue, so we are going to start from all of them. Also we count number of fresh oranges.
  3. Define directions we can go: four of them and put levels = 0.

Now, we traverse our grid, using bfs, using level by level traversal: it means, that each time, when we have some elements in queue, we popleft all of them and put new neighbours to the end. In this way each time we reach line levels += 1, we have nodes with distance which is 1 bigger than previous level. In the end levels - 1 will be our answer, because one time in the end when we do not have anythin to add, levels still be incremented by one.

Finally, we check if we still have fresh oranges, and if yes, return -1. If not, we need to return max(levels-1, 0), because it can happen, that our queue was empty in the beginning and we do not need to subtract 1.

Complexity: time complexity is O(mn), because we first traverse our grid to fill queue and found number of fresh oranges. Then we use classical bfs, so each node will be added and removed from queue at most 1 time. Space complexity is also can be O(mn), we can have for example O(mn) rotten oranges in the very beginnig.

class Solution:
    def orangesRotting(self, grid):
        m, n, queue, fresh = len(grid), len(grid[0]), deque(), 0
        for i,j in product(range(m), range(n)):
            if grid[i][j] == 2: queue.append((i,j))
            if grid[i][j] == 1: fresh += 1
        dirs = [[1,0],[-1,0],[0,1],[0,-1]]
        levels = 0
        
        while queue:
            levels += 1
            for _ in range(len(queue)):
                x, y = queue.popleft()
                for dx, dy in dirs:
                    if 0<=x+dx<m and 0<=y+dy<n and grid[x+dx][y+dy] == 1:
                        fresh -= 1
                        grid[x+dx][y+dy] = 2
                        queue.append((x+dx, y+dy))
                        
        return -1 if fresh != 0 else max(levels-1, 0)

If you like the solution, you can upvote it on leetcode discussion section: Problem 0994