Skip to main content

994. Rotting Oranges

mediumAsked at Amazon

Given a grid of oranges (empty / fresh / rotten), return the minimum minutes until all fresh oranges rot, or -1 if impossible. Amazon asks this to test whether you reach for multi-source BFS — starting from ALL rotten oranges simultaneously.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Amazon loops.

  • Glassdoor (2026-Q1)— Amazon SDE I/II onsite reports cite this as a BFS staple.
  • Blind (2025-10)— Recurring Amazon interview problem.

Problem

You are given an m x n grid where each cell can have one of three values: 0 representing an empty cell, 1 representing a fresh orange, or 2 representing a rotten orange. Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] is 0, 1, or 2.

Examples

Example 1

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

Example 2

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

Example 3

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

Approaches

1. Multi-source BFS (optimal)

Start BFS from ALL rotten oranges at minute 0. Track fresh count. Each minute, rotten cells rot their fresh neighbors and join the queue. Return the minute counter when queue empties.

Time
O(m * n)
Space
O(m * n)
function orangesRotting(grid) {
  const m = grid.length, n = grid[0].length;
  const q = [];
  let fresh = 0;
  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] === 2) q.push([r, c]);
      else if (grid[r][c] === 1) fresh++;
    }
  }
  if (fresh === 0) return 0;
  let minutes = 0;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  while (q.length && fresh > 0) {
    const sz = q.length;
    for (let i = 0; i < sz; i++) {
      const [r, c] = q.shift();
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] === 1) {
          grid[nr][nc] = 2;
          fresh--;
          q.push([nr, nc]);
        }
      }
    }
    minutes++;
  }
  return fresh === 0 ? minutes : -1;
}

Tradeoff: Multi-source BFS is the right tool because all initial rotten oranges spread simultaneously. Single-source BFS from one orange would over-count time.

Amazon-specific tips

Amazon interviewers grade this on multi-source BFS recognition. State out loud: 'Every initial rotten orange is a BFS source at minute 0 — they all spread simultaneously. So I enqueue ALL of them upfront and process level-by-level.' Forgetting that the rotten oranges are simultaneous sources is the #1 conceptual bug.

Common mistakes

  • Single-source BFS from one rotten orange — gets wrong answer.
  • Counting minutes incorrectly (incrementing inside the inner loop instead of after each level).
  • Returning the minute counter when fresh > 0 at the end (should return -1).

Follow-up questions

An interviewer at Amazon may pivot to one of these next:

  • Walls and Gates (LC 286) — same multi-source BFS pattern from gates.
  • 01 Matrix (LC 542) — multi-source BFS from 0-cells.
  • What if some cells could BLOCK the rotting (impassable barriers)?

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why multi-source instead of single-source?

The problem says all rotten oranges spread SIMULTANEOUSLY. Single-source BFS would compute distance from ONE rotten orange, missing the fact that another might be closer.

What if there are no rotten oranges to start?

If fresh > 0 and no sources, return -1. If fresh == 0, return 0 (already done).

Practice these live with InterviewChamp.AI

Drill Rotting Oranges and other Amazon interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →