Rotting Oranges

MediumBFS / GridsMulti-source BFS on a gridbfsgridmulti-source-bfs

Maintained by Vikas Dulgunde, software engineer

You are given a grid of size m by n. Each cell holds one of three values: 0 for an empty cell, 1 for a fresh orange, and 2 for a rotten orange.

Rot spreads in steps. During each minute, every fresh orange that shares an edge with a rotten orange (up, down, left, or right) turns rotten as well. Diagonal neighbours do not count.

Return the smallest number of minutes that must pass before no fresh orange is left. If at least one fresh orange is walled off from all rot and can never turn, return -1 instead.

If the grid starts with no fresh oranges at all, the answer is 0, because there is nothing left to rot.

Examples

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

Output: 4

The single rotten orange at the top-left spreads outward one ring per minute. After minute 1 its two neighbours rot, and the wave continues until the last fresh orange in the bottom-right rots at minute 4.

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

Output: -1

The fresh orange at the bottom-left corner has only empty cells and the grid edge around it, so no rot ever reaches it. Since a fresh orange survives forever, the answer is -1.

Input: grid = [[0,2]]

Output: 0

There are no fresh oranges to begin with, so zero minutes are needed.

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

Output: 2

The rotten orange in the bottom-right rots its two edge neighbours at minute 1, then the remaining top-left orange rots at minute 2.

Constraints

m == grid.length and n == grid[i].length
1 <= m, n <= 10
Each grid[i][j] is 0, 1, or 2
Only 4-directional adjacency counts; diagonals do not spread rot

Visible test cases

orangesRotting([[2,1,1],[1,1,0],[0,1,1]]) == 4
orangesRotting([[2,1,1],[0,1,1],[1,0,1]]) == -1
orangesRotting([[0,2]]) == 0
orangesRotting([[1,1],[1,2]]) == 2
orangesRotting([[2,2],[2,2]]) == 0
orangesRotting([[1]]) == -1

Hints

Hint 1

All rotten oranges spread at the same time, so this is not a single starting point. Think about advancing every rot source together, one ring at a time.

Hint 2

A breadth-first search that begins from every rotten cell at once visits cells in exactly the order they rot. The depth of that search is the number of minutes.

Hint 3

Count the fresh oranges up front. After the search finishes, if any fresh orange remains uncounted as rotted, the spread could not reach it, so return -1.

Loading the editor...

Approaches

Repeated full-grid scan

Time O(m * n * k) where k is the number of minutes, since each minute rescans the whole grid · Space O(m * n) for the list of cells to flip per minute

Simulate one minute at a time by scanning the whole grid, marking every fresh orange adjacent to a rotten one, then applying all of those changes together before the next minute.

Loop a counter for minutes, starting at 0.
On each pass, walk every cell; collect the coordinates of fresh oranges that touch a rotten neighbour.
If nothing new was found, stop the loop.
Otherwise turn all collected cells rotten at once and increment the minute counter.
After the loop, scan once more; if any fresh orange remains return -1, else return the minute counter.

Multi-source BFS

Time O(m * n) since each cell is enqueued and inspected a constant number of times · Space O(m * n) for the queue in the worst case where most cells start rotten

Seed a queue with every rotten orange and process the queue level by level. Each level is one minute of spread, so the number of levels processed is the answer.

Scan once to enqueue all rotten cells and to count the fresh oranges.
If there are no fresh oranges, return 0 immediately.
While the queue is not empty and fresh oranges remain, process the current level: for each cell pop it and look at its four neighbours.
Any fresh neighbour is turned rotten, the fresh count drops by one, and the neighbour is pushed for the next level.
After finishing a level that rotted at least one orange, add one to the minute counter.
When the queue drains, return the minute counter if no fresh orange is left, otherwise return -1.

Common mistakes

Incrementing the minute counter once per orange instead of once per level, which overcounts the time.
Returning the level count when fresh oranges are still walled off; that case must return -1, not the elapsed minutes.
Forgetting the all-rotten or no-fresh starting grid, which should return 0 rather than 1.
Spreading rot one orange at a time within the same minute so a newly rotted orange infects its neighbours in the same step; you must freeze the level boundary before advancing.
Treating diagonal neighbours as adjacent, which lets rot spread faster than the rules allow.

Follow-up variations

What changes if rot can also spread diagonally, giving eight neighbours per cell?
Instead of the total time, can you report which specific fresh oranges can never rot?
If oranges could be added or removed between minutes, how would you keep the answer up to date efficiently?
How would you adapt the approach if each cell had a different rot delay rather than a uniform one minute?

Build the rest of your prep

All coding problems

Practice problems by company

The NeetCode 150 roadmap

Guide: coding interview patterns

Examples

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

Output: 4

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

Output: -1

The fresh orange at the bottom-left corner has only empty cells and the grid edge around it, so no rot ever reaches it. Since a fresh orange survives forever, the answer is -1.

Input: grid = [[0,2]]

Output: 0

There are no fresh oranges to begin with, so zero minutes are needed.

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

Output: 2

The rotten orange in the bottom-right rots its two edge neighbours at minute 1, then the remaining top-left orange rots at minute 2.

Hints

Hint 1

All rotten oranges spread at the same time, so this is not a single starting point. Think about advancing every rot source together, one ring at a time.

Hint 2

A breadth-first search that begins from every rotten cell at once visits cells in exactly the order they rot. The depth of that search is the number of minutes.

Hint 3

Count the fresh oranges up front. After the search finishes, if any fresh orange remains uncounted as rotted, the spread could not reach it, so return -1.

Approaches

Repeated full-grid scan

Time O(m * n * k) where k is the number of minutes, since each minute rescans the whole grid · Space O(m * n) for the list of cells to flip per minute

Simulate one minute at a time by scanning the whole grid, marking every fresh orange adjacent to a rotten one, then applying all of those changes together before the next minute.

Loop a counter for minutes, starting at 0.
On each pass, walk every cell; collect the coordinates of fresh oranges that touch a rotten neighbour.
If nothing new was found, stop the loop.
Otherwise turn all collected cells rotten at once and increment the minute counter.
After the loop, scan once more; if any fresh orange remains return -1, else return the minute counter.

Multi-source BFS

Time O(m * n) since each cell is enqueued and inspected a constant number of times · Space O(m * n) for the queue in the worst case where most cells start rotten

Seed a queue with every rotten orange and process the queue level by level. Each level is one minute of spread, so the number of levels processed is the answer.

Scan once to enqueue all rotten cells and to count the fresh oranges.
If there are no fresh oranges, return 0 immediately.
While the queue is not empty and fresh oranges remain, process the current level: for each cell pop it and look at its four neighbours.
Any fresh neighbour is turned rotten, the fresh count drops by one, and the neighbour is pushed for the next level.
After finishing a level that rotted at least one orange, add one to the minute counter.
When the queue drains, return the minute counter if no fresh orange is left, otherwise return -1.

Common mistakes

Incrementing the minute counter once per orange instead of once per level, which overcounts the time.

Returning the level count when fresh oranges are still walled off; that case must return -1, not the elapsed minutes.

Forgetting the all-rotten or no-fresh starting grid, which should return 0 rather than 1.

Spreading rot one orange at a time within the same minute so a newly rotted orange infects its neighbours in the same step; you must freeze the level boundary before advancing.

Treating diagonal neighbours as adjacent, which lets rot spread faster than the rules allow.

Follow-up variations

What changes if rot can also spread diagonally, giving eight neighbours per cell?

Instead of the total time, can you report which specific fresh oranges can never rot?

If oranges could be added or removed between minutes, how would you keep the answer up to date efficiently?

How would you adapt the approach if each cell had a different rot delay rather than a uniform one minute?

Rotting Oranges

Examples

Constraints

Hints

Approaches

Repeated full-grid scan

Multi-source BFS

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep

Rotting Oranges

Examples

Constraints

Hints

Approaches

Repeated full-grid scan

Multi-source BFS

Common mistakes

Follow-up variations

Recommended problems

Build the rest of your prep