Problem Statement in English

You’re given an $m \times n$ matrix, grid. Each cell can have a value of:

  • $0$: indicating an empty cell
  • $1$: indicating a cell with a fresh fruit
  • $2$: indicating a cell with a rotten fruit

Every minute, fresh fruits that are either in vertical or horizontal contact with rotten fruits also rot. You’ve to return the number of minutes after which all fruits are rotten, or, if that situation isn’t possible, return $-1$.

Approach

The fact that sometimes all fruits may not rot indicates that we deifnitely need to figure out which fruits are fresh, in order to figure out whether they’ve rotted by the time we’re done or not. We also neeed to figure out which fruits are rotten to begin with so that we can fan out from there and track fruits as they rot each minute.

It’s important to note that $1$ minute is basically $1$ level of immediate neighbours. Think about it. When you’re convinced, continue reading.

We also need to keep track of the number of minutes that have elapsed since we started the simulation.

Think of the rot spreading out from, well, a rotten fruit, each minute. The mechanics of that are actually perfect for being modelled by a breadth first search, and that’s what we’re going to be using.

We first need to find all fresh (add to a Set) and rotten fruits (add to a Queue). Once we’ve done that we can start processing fruits in the queue.

We look for all fresh neighbours that are 4 way connected, basically nodes that are above, below, and on the left or right of this node, because at the end of $1$ minute, they’re going to have rotted, so we add them to the Queue, and remove them from our fresh Set, because they’re no longer fresh. THEY’VE DEFECTED!!!! Ahem.

After this we increment minutes, because $1$ minute has passed, and now we may proceed with the new neighbours that are going to have rotted by the end of the next minute.

We keep repeating this process until our Queue is empty. At this point we check if all fruits in the fresh Set have rotted, if not, then we return -1, as there’s no way that all the fruits can rot, otherwise we return minutes.

Solution in Python

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        temp = []
        seen = set()

        rows = len(grid)
        cols = len(grid[0])
        fresh = 0

        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 2:
                    t = (i,j)
                    temp.append(t)
                    seen.add(t)
                elif grid[i][j] == 1:
                    fresh+=1

        if not fresh: return 0
        if not temp: return -1

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

        time = -1

        while temp:
            q = deque(temp)
            temp = []
            time+=1

            while q:
                x,y = q.popleft()
                t = (x,y)

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

                    if 0<=nx<rows and 0<=ny<cols and (nx,ny) not in seen and grid[nx][ny] == 1:
                        fresh-=1
                        temp.append((nx,ny))
                        seen.add((nx,ny))

        return -1 if fresh else time

Note: Using the discard method allows you to attempt to remove elements that aren’t in the Set - if the element isn’t in the Set, then nothing’s removed and no error is thrown. Convenient.

Complexity

  • Time: $O(n^2)$
    Since in the worst case we visit all the elements in the $n \times n$ matrix, and $n*n=n^2$.

  • Space: $O(n^2)$
    Since in the worst case we store all the elements in the $n \times n$ matrix in the Set, and $n*n=n^2$.

And we are done.