Rotting Oranges

Difficulty: Medium

Problem

You are given an m × n grid where each cell holds one of three values: 0 (an empty cell), 1 (a fresh orange), or 2 (a rotten orange). Every minute, every rotten orange rots the fresh oranges 4-directionally adjacent to it — all of them, all simultaneously. Return the number of minutes that pass until no fresh orange remains. If some fresh orange can never rot, return -1.

Example

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4
Explanation: The rot starts in the top-left corner and spreads one ring per minute. The empty cells block the direct routes, so the wave snakes around them and reaches the farthest orange — the bottom-right one — at minute 4.

Brute-force approach

There is no slower-but-sensible alternative here — simulating the rot minute by minute IS the problem, and multi-source BFS is that simulation in its natural form. DFS can't even model simultaneous spreading.

Optimal approach

Key insight: Seed the queue with EVERY rotten orange. Each BFS wave is exactly one minute of rot. The clock and the algorithm are the same thing.

Seed the queue with every rotten orange, count the fresh ones, then let BFS spread the rot one full wave per minute. When the simulation stops, the fresh counter delivers the verdict: 0 means return minutes, anything else means -1.

Steps

  1. Scan the grid once: enqueue every rotten cell, count every fresh cell
  2. While the queue has cells AND fresh oranges remain, process one full wave — snapshot len(queue) first
  3. Each popped cell infects its 4-directional fresh neighbors: mark rotten immediately, fresh -= 1, enqueue
  4. After each full wave, minutes += 1 — one wave is one minute
  5. Return minutes if fresh == 0, otherwise -1 — someone was walled off

Time complexity: O(rows × cols) · Space complexity: O(rows × cols) queue