Rotting Oranges

Rot spreads from bad oranges to their neighbors once a minute. Work out how long until every orange is rotten, or report that some never will be. Multi-source BFS in a grid. Solve it below in Python or JavaScript, then read the walkthrough.

MediumArray Breadth-First Search Matrix Asked at 142 companies incl. Google, Amazon, Meta

Problem

You're given an m × n grid where each cell holds one of three values:

0: an empty cell
1: a fresh orange
2: a rotten orange

Every minute, each fresh orange that shares an edge (up, down, left, or right) with a rotten orange becomes rotten. All of these changes happen at the same time.

Return the number of minutes until no fresh orange is left. If some fresh orange can never be reached by the rot, return -1. If there are no fresh oranges to begin with, the answer is 0.

Example 1

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

The rot starts in the top-right corner and needs four minutes to wind its way to the bottom-left orange.

Example 2

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

The empty cell separates the fresh orange from the rotten one, so it never rots.

Example 3

Input: grid = [[0, 0], [0, 0]]
Output: 0

There are no fresh oranges, so no time needs to pass.

Constraints

1 ≤ m, n ≤ 10
grid[i][j] is 0, 1, or 2.

Practice

Runs 11 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.

Get asked Rotting Oranges in a real interview?

Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.

Start Free Trial

How to solve Rotting Oranges

Pattern: Multi-source BFS

Anything that "spreads one step per tick to its neighbors" is breadth-first search, where each BFS level is one tick. The twist here is that the rot starts from several places at once.

You don't need to run a BFS from each rotten orange. Put all of them in the queue at the start, as level 0. BFS then expands every source in lockstep, which is exactly the "all changes happen at the same time" rule. The number of levels you process before the queue empties is the answer, and if you also count fresh oranges up front, you know at the end whether any were never reached.

Approach 1: Repeated full-grid simulation

Each minute, scan the whole grid and mark every fresh orange next to a rotten one (writing to a copy so changes in this minute do not spread further in the same minute). Stop when nothing changes. Simple, but in the worst case the rot needs O(m·n) minutes and each minute rescans the grid.

Time O((m·n)²) · Space O(m·n)

Approach 2: Multi-source BFS

Scan once: push every rotten cell into a queue and count the fresh oranges.
If there are none fresh, return 0.
Process the queue one level at a time. For each cell, rot any fresh neighbor, decrement the fresh count, and push it.
After each level that rotted at least one orange, add a minute.

Return the minutes if the fresh count reached zero, otherwise -1. Each cell enters the queue at most once.

Time O(m·n) · Space O(m·n)

Approach	Time	Space
Repeated full-grid simulation	O((m·n)²)	O(m·n)
Multi-source BFS	O(m·n)	O(m·n)

Solution code

Try the practice editor first. Both solutions pass every test above.

Rotting Oranges solution in Python

from collections import deque


def oranges_rotting(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh > 0:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
        minutes += 1
    return minutes if fresh == 0 else -1

Rotting Oranges solution in JavaScript

function orangesRotting(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  let queue = [];
  let fresh = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) queue.push([r, c]);
      else if (grid[r][c] === 1) fresh++;
    }
  }
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let minutes = 0;
  while (queue.length && fresh > 0) {
    const next = [];
    for (const [r, c] of queue) {
      for (const [dr, dc] of dirs) {
        const nr = r + dr;
        const nc = c + dc;
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
          grid[nr][nc] = 2;
          fresh--;
          next.push([nr, nc]);
        }
      }
    }
    queue = next;
    minutes++;
  }
  return fresh === 0 ? minutes : -1;
}

Common mistakes

Running a separate BFS from each rotten orange and taking a maximum, which gives the wrong answer because each fresh orange should rot from its nearest source.
Counting a minute for the final level even though it rotted nothing, which makes the answer one too large.
Returning `-1` when there are no fresh oranges at all. The answer is `0`.
Rotting neighbors in place during a full-grid scan without a copy, so rot travels several cells in a single minute.

What interviewers look for

Name the pattern in one breath: "the rot spreads one step per minute from several starting points, so it's a BFS with all the rotten oranges as sources, and the number of levels is the time." That shows you recognize both the BFS and why the sources start together.

Mention the fresh-orange counter early. It replaces a second scan of the grid at the end and makes the -1 case fall out naturally. Then walk through the three special cases: no fresh oranges, an unreachable orange, and a grid with no rotten oranges.

Follow-up questions

What if you need the time at which each orange rots?

Keep a distance grid initialized to -1 and set `dist[neighbor] = dist[cell] + 1` when you push. That is the same BFS, and the answer is the largest distance.

What if rot can also spread diagonally?

Use eight neighbor offsets instead of four. Nothing else changes, and the complexity stays O(m·n).

What if some oranges take two minutes to rot instead of one?

Edges now have different weights, so plain BFS no longer gives correct times. Use Dijkstra with a min-heap, or 0-1 BFS style bucketing since the weights are small integers.

Companies that ask Rotting Oranges

Rotting Oranges is tagged by 142 companies in our interview dataset. The score shows how often it comes up at each company.

and 118 more.

Get live help in the real interview

Working solutions in real time during your actual interview. Invisible to screensharing.

Start Free Trial

No credit card required

Rotting Oranges

MediumArray Breadth-First Search Matrix Asked at 142 companies incl. Google, Amazon, Meta

Problem

You're given an m × n grid where each cell holds one of three values:

0: an empty cell
1: a fresh orange
2: a rotten orange

Every minute, each fresh orange that shares an edge (up, down, left, or right) with a rotten orange becomes rotten. All of these changes happen at the same time.

Return the number of minutes until no fresh orange is left. If some fresh orange can never be reached by the rot, return -1. If there are no fresh oranges to begin with, the answer is 0.

Example 1

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

The rot starts in the top-right corner and needs four minutes to wind its way to the bottom-left orange.

Example 2

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

The empty cell separates the fresh orange from the rotten one, so it never rots.

Example 3

Input: grid = [[0, 0], [0, 0]]
Output: 0

There are no fresh oranges, so no time needs to pass.

Constraints

1 ≤ m, n ≤ 10
grid[i][j] is 0, 1, or 2.

Practice

Runs 11 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.

Get asked Rotting Oranges in a real interview?

Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.

Start Free Trial

How to solve Rotting Oranges

Pattern: Multi-source BFS

Anything that "spreads one step per tick to its neighbors" is breadth-first search, where each BFS level is one tick. The twist here is that the rot starts from several places at once.

Approach 1: Repeated full-grid simulation

Time O((m·n)²) · Space O(m·n)

Approach 2: Multi-source BFS

Scan once: push every rotten cell into a queue and count the fresh oranges.
If there are none fresh, return 0.
Process the queue one level at a time. For each cell, rot any fresh neighbor, decrement the fresh count, and push it.
After each level that rotted at least one orange, add a minute.

Return the minutes if the fresh count reached zero, otherwise -1. Each cell enters the queue at most once.

Time O(m·n) · Space O(m·n)

Approach	Time	Space
Repeated full-grid simulation	O((m·n)²)	O(m·n)
Multi-source BFS	O(m·n)	O(m·n)

Solution code

Try the practice editor first. Both solutions pass every test above.

Rotting Oranges solution in Python

from collections import deque


def oranges_rotting(grid: list[list[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh > 0:
        for _ in range(len(queue)):
            r, c = queue.popleft()
            for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    queue.append((nr, nc))
        minutes += 1
    return minutes if fresh == 0 else -1

Rotting Oranges solution in JavaScript

function orangesRotting(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  let queue = [];
  let fresh = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === 2) queue.push([r, c]);
      else if (grid[r][c] === 1) fresh++;
    }
  }
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let minutes = 0;
  while (queue.length && fresh > 0) {
    const next = [];
    for (const [r, c] of queue) {
      for (const [dr, dc] of dirs) {
        const nr = r + dr;
        const nc = c + dc;
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === 1) {
          grid[nr][nc] = 2;
          fresh--;
          next.push([nr, nc]);
        }
      }
    }
    queue = next;
    minutes++;
  }
  return fresh === 0 ? minutes : -1;
}

Common mistakes

Running a separate BFS from each rotten orange and taking a maximum, which gives the wrong answer because each fresh orange should rot from its nearest source.
Counting a minute for the final level even though it rotted nothing, which makes the answer one too large.
Returning `-1` when there are no fresh oranges at all. The answer is `0`.
Rotting neighbors in place during a full-grid scan without a copy, so rot travels several cells in a single minute.

What interviewers look for

Follow-up questions

What if you need the time at which each orange rots?

Keep a distance grid initialized to -1 and set `dist[neighbor] = dist[cell] + 1` when you push. That is the same BFS, and the answer is the largest distance.

What if rot can also spread diagonally?

Use eight neighbor offsets instead of four. Nothing else changes, and the complexity stays O(m·n).

What if some oranges take two minutes to rot instead of one?

Edges now have different weights, so plain BFS no longer gives correct times. Use Dijkstra with a min-heap, or 0-1 BFS style bucketing since the weights are small integers.

Companies that ask Rotting Oranges

Rotting Oranges is tagged by 142 companies in our interview dataset. The score shows how often it comes up at each company.

and 118 more.

Get live help in the real interview

Working solutions in real time during your actual interview. Invisible to screensharing.

Start Free Trial

No credit card required

Problem

Constraints

Practice

How to solve Rotting Oranges

Approach 1: Repeated full-grid simulation

Approach 2: Multi-source BFS

Solution code

Common mistakes

What interviewers look for

Follow-up questions

What if you need the time at which each orange rots?

What if rot can also spread diagonally?

What if some oranges take two minutes to rot instead of one?

Companies that ask Rotting Oranges

Practice next

Get live help in the real interview

Problem

Constraints

Practice

How to solve Rotting Oranges

Approach 1: Repeated full-grid simulation

Approach 2: Multi-source BFS

Solution code

Common mistakes

What interviewers look for

Follow-up questions

What if you need the time at which each orange rots?

What if rot can also spread diagonally?

What if some oranges take two minutes to rot instead of one?

Companies that ask Rotting Oranges

Practice next

Get live help in the real interview