Coding · Graphs and grids
Rotting Oranges
- Reported once
- Medium
- Intern
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
A grid holds 0 for an empty cell, 1 for a fresh orange and 2 for a rotten one, and every minute each fresh orange that touches a rotten one (up, down, left or right) becomes rotten. Return the number of minutes until no fresh orange is left, or -1 if some orange can never rot. For [[2,1,1],[1,1,0],[0,1,1]] the answer is 4. The grid can be as large as 1,000 by 1,000.
Restated in our own words, not a quote from Razorpay or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: are all rows the same length? Does rot spread only in the four straight directions, or diagonally too? Does every rotten orange spread at the same moment each minute? What should I return when there is no fresh orange to begin with, or no rotten one? Can the grid be empty? How big can it get?
I would assume a rectangular grid, four-direction spread, all spreading at once each minute, an answer of 0 when nothing is fresh, and -1 when a fresh orange can never be reached. I would also keep the caller's grid unchanged.
Brute force
Say the obvious answer and why it is too slow.
Simulate it literally. Each minute, scan the whole grid, find every fresh orange next to a rotten one, mark them all in a copy, then swap the copy in. Stop when a pass changes nothing, then check whether any fresh orange remains.
One pass costs O(R×C). The number of minutes can be as large as the number of cells, because rot can crawl along a winding corridor of fresh oranges one cell per minute. That gives O((R×C)²) in the worst case. On a 1,000 by 1,000 grid that is a million cells times hundreds of thousands of minutes, far too slow, and almost all of the scanning re-checks cells that are nowhere near the rot front.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O((R×C)²)
- Time
- O(R×C)
- Space
- O(R×C)
The pattern is multi-source BFS on a grid. Rot spreads outward from every rotten orange at once, one step per minute, which is exactly how breadth-first search expands level by level. The only twist is that the search starts from many cells instead of one: put all the initially rotten oranges in the first level.
Why it is correct: BFS visits cells in order of their distance from the nearest source. A fresh orange first reached on level k cannot have been reachable on any earlier level, because every cell of level k-1 and earlier was fully expanded first. So the level number at which an orange rots is exactly the minute it rots, and the answer is the level of the last orange to rot. If the queue runs dry while some fresh orange remains, nothing can reach it (walled off by empty cells), so the answer is -1.
Two details matter. First, mark an orange rotten when you add it to the next level, not when you take it out, so no cell is queued twice. Second, count fresh oranges up front and stop as soon as that count hits zero, otherwise the final level, which spreads to nothing, adds one minute too many. I would say it aloud as: all rotten cells are minute zero, and each round of the loop is one minute.
Walk it through
A dry run on the example, step by step.
| Minute | Cells that rot | Fresh left | Minutes counted |
|---|---|---|---|
| 0 (start) | (0,0) already rotten | 6 | 0 |
| 1 | (0,1) (1,0) | 4 | 1 |
| 2 | (0,2) (1,1) | 2 | 2 |
| 3 | (2,1) | 1 | 3 |
| 4 | (2,2) | 0 | 4 |
Use [[2,1,1],[1,1,0],[0,1,1]]. At the start the only rotten cell is (0,0) and there are 6 fresh oranges. The trace table shows each round.
Minute 1: (0,0) rots its two neighbors (0,1) and (1,0). Minute 2: (0,1) rots (0,2) and (1,1); (1,0) also touches (1,1), but it is already rotten, so it is not counted twice. Minute 3: (1,1) rots (2,1), while (0,2) has no fresh neighbor because (1,2) is empty. Minute 4: (2,1) rots (2,2). Fresh count reaches 0 and the loop stops with 4 minutes. Notice that the table counts rounds, not oranges: six oranges rot, but only four minutes pass.
The code
Runnable JavaScript, checked against test cases.
function orangesRotting(grid) {
const rows = grid.length;
const cols = rows === 0 ? 0 : grid[0].length;
const cells = grid.map((row) => row.slice());
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let frontier = [];
let fresh = 0;
for (let r = 0; r < rows; r++) {
for (let c = 0; c < cols; c++) {
if (cells[r][c] === 2) frontier.push([r, c]);
else if (cells[r][c] === 1) fresh++;
}
}
let minutes = 0;
while (frontier.length > 0 && fresh > 0) {
const next = [];
for (const [r, c] of frontier) {
for (const [dr, dc] of directions) {
const nr = r + dr;
const nc = c + dc;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
if (cells[nr][nc] !== 1) continue;
cells[nr][nc] = 2;
fresh--;
next.push([nr, nc]);
}
}
frontier = next;
minutes++;
}
return fresh === 0 ? minutes : -1;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
No fresh orange at all: the loop condition is false straight away and the answer is 0, even if there are no rotten ones either. An empty grid has zero rows, so it also returns 0.
Fresh oranges but no rotten one: the frontier starts empty, the loop never runs, fresh stays above zero and the result is -1.
A fresh orange fenced off by empty cells (or by the grid edge): the frontier empties while fresh is still above zero, so the loop ends and the code returns -1.
A single cell, or a grid with only rotten and empty cells, returns 0. The code copies the grid first, so the caller's input is never changed. Bounds are checked before every read, so edge and corner cells need no special case.
Follow-ups to expect
Where the interviewer pushes next.
- How would you change the code if rot could also spread diagonally, or if some cells were walls that block it?
- What if each fresh orange needed its own number of minutes before it rots once touched, which algorithm replaces BFS?
- How would you return the grid as it looks after exactly k minutes?
- Why would a depth-first search give wrong minutes here even though it reaches every reachable orange?
- How would you handle new rotten oranges appearing at given times while the rot is already spreading?
Where candidates slip
The mistakes this problem punishes.
One easy slip is counting minutes per orange taken from the queue instead of per level, which inflates the answer. The second is the off-by-one at the end: incrementing the minute counter after the last level that rotted nothing, so every answer is one too large. Stopping when fresh reaches zero avoids it.
Others: marking a cell rotten only when it is dequeued, so the same cell is queued several times; forgetting the -1 case by returning the last level even though some orange was never reached; using DFS, which finds some path but not the shortest one; and using queue.shift() on a huge array, which can be slow when the queue is large. Processing level arrays, as the code does, sidesteps it.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.