Rotten oranges problem

Tags: , ,

Rotten oranges problem goes like: In a given grid, each cell can have one of three values:

  • the value 0 representing an empty cell;
  • the value 1 representing a fresh orange;
  • the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange.  If this is impossible, return -1 instead.

Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Input: [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten because rotting only happens 4-directionally.

rotten oranges

Thoughts

Rotting oranges problem offers a unique perspective on identifying a graph search problem. At first glance, it seems like the solution to the problem lies in changing the status of the given grid on multiple time steps while counting the steps and making sure that we come to a conclusion to our iterations, akin to solving a sudoku puzzle, where the state of the entire grid matters.

On further inspection though, we can see that we do not need to worry about the state of the entire grid, just the fresh oranges adjacent newly rotting oranges at each time step. We can consider the oranges as nodes of a graph, and the fresh oranges around them as connected to these nodes. We do not know the entire state of the graph beforehand, but we know that the adjacent nodes will expose themselves as time passes. This pushes us towards the idea of a Breadth-First Search, where we topologically move level by level through a graph.

This problem also has some interesting edge cases, with it being necessary to parse the graph to identify such cases:

Invalid grid return -1
Grid with all rotten oranges return 0
Grid with no rotten oranges and no fresh return 0
Grid with no rotten oranges and fresh present return -1
Grid post BFS with fresh oranges left return -1
Grid post BFS with all rotten oranges return count

Show me the implementation

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        # Make sure we have a valid grid
        if len(grid) < 1 or len(grid[0]) < 1:
            return -1
        sources = []
        ones = 0
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == 2:
                    sources.append((i, j))
                elif grid[i][j] == 1:
                    ones += 1
        if len(sources) == 0:
            # In case of no rotten oranges, return value depending 
            # on the state of the grid
            if ones == 0:
                return 0
            else:
                return -1
        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        # Grid is initially at t = -1
        count = -1
        visited = set(sources)
        # End the BFS when there are no new sources left
        while len(sources) > 0:
            count += 1
            newsources = []
            for source in sources:
                i, j = source
                grid[i][j] = 2
                for direction in directions:
                    row = i + direction[0]
                    col = j + direction[1]
                    # Make sure it is a valid row and column,
                    # It is not visited, and it is a fresh orange
                    if row >= 0 and row < len(grid) \
                       and col >= 0 and col < len(grid[0]) \
                       and (row, col) not in visited and grid[row][col] == 1:
                        newsources.append((row, col))
                        visited.add((row, col))
            sources = newsources
        # Make sure there are no fresh oranges left in the grid
        for i in grid:
            for j in i:
                if j == 1:
                    return -1
        return count

The runtime complexity of BFS is O(V + E), which in our scenario translates to moving to every node, i.e. O(n * m) where n and m are dimensions of the grid. The space complexity of BFS is O(V), which similarly as time complexity translates into O(n*m)

This article is contributed by Khushman Patel