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

Hiring now

Meesho has 33 open roles right now

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Deputy Manager- FP&A
Bangalore, Karnataka
Security Engineer III - Infra Security
Bangalore, Karnataka
Product Manager I
Bangalore, Karnataka

Or practice this question first

Next question