Rotting Oranges LeetCode Solution (Medium) (2026)

Approach Summary

Multi-source BFS starting from all rotten oranges simultaneously. Count BFS levels (minutes).

Practice Mode

Solve it yourself before revealing the code

DSA interviews test reasoning from brute force to optimal. Think through the constraints first.

Full Solution & Approach

All rotten oranges spread simultaneously, one cell per minute — that is exactly a multi-source BFS where the level count equals the elapsed minutes. Seed the queue with every initially rotten orange and count the fresh ones. Process the queue level by level: for each rotten orange at the current level, rot its four-directional fresh neighbors, add them to the next level, and decrement the fresh count. Track the number of levels processed as minutes. When the queue empties, if any fresh oranges remain they were unreachable (separated by empty cells) — return -1. Otherwise return the minute count, or 0 if there were never any fresh oranges. The BFS-levels-as-time trick is the standard way to simulate simultaneous spread, and the same skeleton solves shortest-step problems on grids.

Each cell is enqueued at most once — O(m × n) time. The queue holds at most the frontier of rotten cells — O(m × n) worst case.

Solution Code

Solution

public int orangesRotting(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    Deque<int[]> queue = new ArrayDeque<>();
    int fresh = 0;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 2) queue.offer(new int[]{i, j});
            else if (grid[i][j] == 1) fresh++;
        }
    int minutes = 0;
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    while (!queue.isEmpty() && fresh > 0) {
        minutes++;
        int size = queue.size();
        for (int s = 0; s < size; s++) {
            int[] cell = queue.poll();
            for (int[] d : dirs) {
                int ni = cell[0] + d[0], nj = cell[1] + d[1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == 1) {
                    grid[ni][nj] = 2;
                    fresh--;
                    queue.offer(new int[]{ni, nj});
                }
            }
        }
    }
    return fresh == 0 ? minutes : -1;
}

int orangesRotting(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    queue<pair<int,int>> q;
    int fresh = 0;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 2) q.push({i, j});
            else if (grid[i][j] == 1) fresh++;
        }
    int minutes = 0;
    int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    while (!q.empty() && fresh > 0) {
        minutes++;
        int size = q.size();
        for (int s = 0; s < size; s++) {
            auto [i, j] = q.front(); q.pop();
            for (auto& d : dirs) {
                int ni = i + d[0], nj = j + d[1];
                if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] == 1) {
                    grid[ni][nj] = 2;
                    fresh--;
                    q.push({ni, nj});
                }
            }
        }
    }
    return fresh == 0 ? minutes : -1;
}

def oranges_rotting(grid: list[list[int]]) -> int:
    from collections import deque
    m, n = len(grid), len(grid[0])
    queue = deque()
    fresh = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == 2:
                queue.append((i, j))
            elif grid[i][j] == 1:
                fresh += 1
    minutes = 0
    while queue and fresh:
        minutes += 1
        for _ in range(len(queue)):
            i, j = queue.popleft()
            for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                ni, nj = i + di, j + dj
                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
                    grid[ni][nj] = 2
                    fresh -= 1
                    queue.append((ni, nj))
    return minutes if fresh == 0 else -1

function orangesRotting(grid) {
  const m = grid.length, n = grid[0].length;
  const queue = [];
  let fresh = 0;
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 2) queue.push([i, j]);
      else if (grid[i][j] === 1) fresh++;
    }
  }
  let minutes = 0;
  while (queue.length && fresh) {
    minutes++;
    const size = queue.length;
    for (let k = 0; k < size; k++) {
      const [i, j] = queue.shift();
      for (const [di, dj] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
        const ni = i + di, nj = j + dj;
        if (ni >= 0 && ni < m && nj >= 0 && nj < n && grid[ni][nj] === 1) {
          grid[ni][nj] = 2;
          fresh--;
          queue.push([ni, nj]);
        }
      }
    }
  }
  return fresh === 0 ? minutes : -1;
}

Edge Cases to Watch

No fresh oranges at the start — return 0
A fresh orange isolated by empty cells — return -1
A single rotten orange in a large grid — minutes equal the longest distance
Empty grid — return 0

Algorithmic Pattern

Master the Queue / BFS Pattern

View Pattern Guide →

Study the core invariant, step-by-step decision framework, and common interview traps for the Queue / BFS pattern.

Framework: Queue / BFS • Interview Prep: Tested at FAANG • Explore all Queue / BFS problems & invariants →

How to Recognize This Pattern

Simultaneous spread from multiple sources
BFS levels = time

Complexity Analysis

Time Complexity

O(m × n)

Space Complexity

O(m × n)

Frequently Asked Questions

What is the optimal time and space complexity for Rotting Oranges?

The optimal solution for Rotting Oranges achieves O(m × n) runtime complexity and requires O(m × n) auxiliary space. Each cell is enqueued at most once — O(m × n) time. The queue holds at most the frontier of rotten cells — O(m × n) worst case.

How do I identify that Rotting Oranges requires the Queue / BFS pattern?

In technical interviews, look for key problem signals: Simultaneous spread from multiple sources; BFS levels = time. Recognizing these invariants allows you to bypass naive brute-force exhaustive search in favor of Queue / BFS strategy.

What critical edge cases must be handled in Rotting Oranges?

Essential edge cases to verify include: No fresh oranges at the start — return 0; A fresh orange isolated by empty cells — return -1; A single rotten orange in a large grid — minutes equal the longest distance; Empty grid — return 0. Always walk through these scenarios with your interviewer before coding.

Which tech companies frequently ask Rotting Oranges?

Rotting Oranges is a Medium-difficulty question tagged with high recurrence. It is actively asked in technical screening and onsite interview loops at Amazon, Google.

Rotting Oranges LeetCode Solution