PPractick

The problem

A crate of oranges is a grid: 0 is empty, 1 is a fresh orange, 2 is a rotten orange. Every minute, each rotten orange rots its 4-directionally adjacent fresh neighbours. How many minutes until no fresh orange remains? Return −1 if some can never rot. All rotten oranges spread at the same time, so this is a multi-source BFS: put every initially rotten orange in the queue at minute 0 and process the queue level by level, with each level being one minute.

Example: [[2,1,1], [1,1,0], [0,1,1]] → 4.

Function signature

int orangesRotting(vector<vector<int>> grid);

Test cases

Input	Output	Explanation
[[2,1,1],[1,1,0],[0,1,1]]	4	The bottom-right orange rots last
[[2,1,1],[0,1,1],[1,0,1]]	-1	The bottom-left orange is cut off
[[2,2],[1,1],[0,0],[2,0]]	1	Several starting points at once
[[0,2]]	0	No fresh oranges to begin with
[[1]]	-1	No rotten orange to start the spread

(Confirm: spreading is 4-directional and simultaneous; 0 if there are no fresh oranges; grid up to 10 × 10.)

How interviewers phrase it

• "Return the minimum number of minutes that must elapse until no cell has a fresh orange; if impossible, return −1" (LeetCode 994).

Clarifying questions to ask

1. 4-directional? (Yes.)
2. What if there are no fresh oranges at all? (0.)
3. Do all rotten oranges spread simultaneously? (Yes, which is why it's multi-source BFS.)

Follow-ups to expect

1. "Why multi-source BFS?"
2. "How do you count minutes?"
3. "How do you detect −1?"
4. "Why not BFS from each rotten orange separately?"
5. "Complexity?"

Related questions

• Flood fill algorithm Medium
• Distance of nearest cell having one Medium
• Surrounded Regions Medium
• Number of enclaves Medium
• Number of islands Medium
• Shortest Distance in a Binary Maze Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in