Rotten Oranges — Day 3 (Python)

Photo by Brienne Hong on Unsplash

The rotten oranges question is one of the most frequently asked questions in interviews especially Amazon. Let’s dive into the question.

994. Rotting Oranges

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.

Example 1:

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

Example 2:

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.

Example 3:

Input: [[0,2]]
Output: 0
Explanation:  Since there are already no fresh oranges at minute 0, the answer is just 0.

Note:

1. 1 <= grid.length <= 10
2. 1 <= grid[0].length <= 10
3. grid[i][j] is only 0, 1, or 2.

I have learned to use Breadth-First-Search Algorithm to be used when we need to find minimum distance or minimum time to do some tasks in a grid or Tree.

In the above question, we need to find the minimum time required for all the oranges rot hence we would be using BFS to solve the above problem.

In order to solve BFS, we require a stack and a queue. Usually, BFS is solved using the Iterative approach. Solving BFS using recursion is of higher complexity.

Let us jump into the solution.

We would require a queue that will hold the co-ordinates of rotten oranges and a set that will hold the co-ordinates of fresh oranges.

 fresh_set = set()
 rotten = []
 for row in range(len(grid)):
     for col in range(len(grid[row])):
         if grid[row][col] == 2:
             rotten.append((row, col, 0))
         elif grid[row][col] == 1:
             fresh_set.add((row, col))

In this question, neighbors are considered as blocks which are adjacent in a 4-direction fashion. We need to calculate possible neighbors.

valid_row = [-1, 0, 0, 1]
valid_col = [0, -1, 1, 0]

Until our queue has elements we pop the co-ordinates from the front of the queue. Keep track of steps taken too. Check if any of the neighbors have fresh orange in them, if yes, push the co-ordinate to the queue and remove it from the fresh set.

If the queue is empty check if there are any more fresh oranges. If yes, return -1(this is what the question requires us to do). Else return the step number.

while(rotten):
    row, col, time = rotten.pop(0)
    for neigh in range(len(valid_row)):
        new_row = row+valid_row[neigh]
        new_col = col+valid_col[neigh]
        # Checks if the orange at this position is fresh and the co-ordinates are not outside the boundary
        if(self.is_safe(new_row, new_col, grid)):
            grid[new_row][new_col] = 2
            rotten.append((new_row, new_col, time+1))
            fresh_set.remove((new_row, new_col))
 return -1 if fresh_set else time

The complete solution is as follows.

class Solution:
    def is_safe(self, row, col, grid):
        return(0<= row< len(grid) and
               0<= col< len(grid[0]) and
               grid[row][col] == 1)
    def orangesRotting(self, grid: List[List[int]]) -> int:
        fresh_set = set()
        rotten = []
        for row in range(len(grid)):
            for col in range(len(grid[row])):
                if grid[row][col] == 2:
                    rotten.append((row, col, 0))
                elif grid[row][col] == 1:
                    fresh_set.add((row, col))
        if rotten == [] and not fresh_set:
            return 0
        elif rotten == []:
            return -1
            
        valid_row = [-1, 0, 0, 1]
        valid_col = [0, -1, 1, 0]
        while(rotten):
            row, col, time = rotten.pop(0)
            for neigh in range(len(valid_row)):
                new_row = row+valid_row[neigh]
                new_col = col+valid_col[neigh]
                if(self.is_safe(new_row, new_col, grid)):
                    grid[new_row][new_col] = 2
                    rotten.append((new_row, new_col, time+1))
                    fresh_set.remove((new_row, new_col))
        return -1 if fresh_set else time

Complexity Analysis

Time Complexity

We are required to scan through each block in the grid. Scanning through each block would take O(N*M), where N is the number of rows and M is the number of columns.

Space Complexity

In the worst-case scenario, we have all the oranges in our grid as rotten. Then we would be required to store the co-ordinates in our queue and that would take O(N * M) where N is the number of rows of the grid and M is the number of columns.

Kindly let me know in case you find any errors in the article. Additionally, I would like to improve my writing skills so any suggestions or critiques are highly welcomed.