< Back




994. Rotting Oranges

We're given an m x n grid of rotting and fresh oranges, and empty spaces. We're asked to determine
the minimum number of minutes it will take for all oranges in the grid to turn rotten. Oranges only
rot and spread rot in 4 directions, adjacent - up, down, left, and right.

We need to spread the rot from all rotten oranges simultaneously. To do this, we'll use BFS starting
from the rotten oranges. We conduct an O(m * n) search of the grid for rotten oranges, and we also
keep track of the fresh oranges.

We BFS from the rotten oranges, incrementing our time counter each time we visit a new level in the
search. For valid neighbors of the current rotten orange, if the orange is fresh or hasn't been
visited previously, we mark it as rotten, visited, and add it to the queue for the next level.

If fresh oranges still exist, we return -1. If nothing has been visited, we never searched, so we
return 0. Otherwise, we return the number of minutes it took to rot all oranges.

The solution is as follows:


  class Solution:
      def orangesRotting(self, grid: List[List[int]]) -> int:
          m, n = len(grid), len(grid[0])

          def is_valid(p: int, q: int) -> bool:
              return -1 < p < m and -1 < q < n and grid[p][q] != 0

          fresh = set()
          seen = set()
          queue = []

          for i in range(m):
              for j in range(n):
                  if grid[i][j] == 2:
                      seen.add((i, j))
                      queue.append((i, j))
                  elif grid[i][j] == 1:
                      fresh.add((i, j))

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

          while queue:
              curr_queue, queue = queue, []
              ans += 1

              for y, x in curr_queue:
                  for dy, dx in directions:
                      ny, nx = y + dy, x + dx

                      if is_valid(ny, nx) and (ny, nx) not in seen and (ny, nx) in fresh:
                          seen.add((ny, nx))
                          queue.append((ny, nx))
                          fresh.discard((ny, nx))

          if fresh:
              return -1

          if not seen:
              return 0

          return ans


_ Time Complexity:

  O(m * n) - We search the entire grid for rotten and fresh oranges.

_ Space Complexity:

  O(m * n) - We could store all oranges in a set of size m * n in the worst case.