Coding

Rotten Oranges

Asked at

Amazon

Informatica

Meesho

MicrosoftPGPrincipal Global Services

Uber

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given an n x m grid, where each cell has the following values :

2 - represents a rotten orange 1 - represents a Fresh orange 0 - represents an Empty Cell Every minute, if a fresh orange is adjacent to a rotten orange in 4-direction ( upward, downwards, right, and left ) it becomes rotten.

Return the minimum number of minutes required such that none of the cells has a Fresh Orange. If it's not possible, return -1.

Input: grid = [ [2, 1, 1] , [0, 1, 1] , [1, 0, 1] ] Output: -1 Explanation: Orange at (3,0) cannot be rotten.

Input: grid = [ [2,1,1] , [1,1,0] , [0,1,1] ] Output: 4 Explanation:

Input: grid = [[0,1,2],[0,1,2],[2,1,1]]

1 <= n, m <= 500
grid[i][j] == 0 or 1 or 2

cpp

class Solution{
public:
    int orangesRotting(vector<vector<int>> &grid) {
       
    }
};

java

class Solution {
    public int orangesRotting(int[][] grid) {
     
    }
}

python

class Solution:
    def orangesRotting(self, grid):

javascript

class Solution {
    orangesRotting(grid) {
      
    }
}

csharp

public class Solution {
    public int OrangesRotting(int[][] grid) {

    }
}

func orangesRotting(grid [][]int) int {
	
}

Stuck? Show a way to structure it+

01Enqueue every initially rotten orange and count all fresh oranges.
02Run BFS in four directions, infecting each fresh orange at most once.
03Track the infection time by BFS level or store a timestamp with each queued cell.
04Return the elapsed time when the fresh count reaches zero; otherwise return -1.

Reference answer

All initially rotten oranges spread at the same time, so this is a multi-source BFS. Scan the grid once. Add every cell containing 2 to the queue and count cells containing 1. If there are no fresh oranges, return 0.

Process the queue in BFS layers. For each rotten cell, inspect its four neighbors. When a neighbor is fresh, change it to rotten immediately, decrement the fresh count, and enqueue it. Marking it when enqueued prevents two sources from processing the same orange. Each completed BFS expansion represents one minute; alternatively, store the minute alongside each queued cell and keep the largest value.

After BFS, return the elapsed minutes if the fresh count is zero. If fresh oranges remain, walls or empty cells isolated them from every source, so return -1. Be careful not to add an extra minute after the final useful layer.

Each cell is scanned and enqueued at most once, giving O(nm) time and O(nm) worst-case queue space.

Then expect these follow-ups

How would you return the minute at which every reachable orange rots?
Tests: BFS state design
Why is running BFS independently from each rotten orange inefficient?
Tests: complexity analysis

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question