DSA problem
Rotting Oranges
You are given an m x n grid where each cell contains exactly one of three values: 0 for an empty cell, 1 for a fresh orange, and 2 for a rotten orange. Every minute any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten itself.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If it is impossible for every fresh orange to become rotten — for example because a fresh orange is unreachable from any rotten one — return -1.
This is the canonical multi-source BFS pattern. All initially rotten oranges decay simultaneously, so they all start at "time = 0". Run BFS where the source set is every rotten orange at once; each BFS level corresponds to one minute elapsing. The level reached when the queue empties is the minute the last orange rots.
The optimal approach first scans the grid to enqueue every rotten orange and count the fresh ones. Then it BFS-expands by levels: each iteration of the outer loop is one minute; we pop the entire current level, rot every fresh 4-neighbour, decrement the fresh count, and enqueue the newly rotten cells. After the queue is empty, if fresh remains the answer is -1; otherwise it is the number of completed levels (subtract one if we counted the initial level as a minute). This runs in O(m * n) time and O(m * n) space.
Examples
grid = [[2,1,1],[1,1,0],[0,1,1]]4grid = [[2,1,1],[0,1,1],[1,0,1]]-1grid = [[0,2]]0Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 10
- gridi is 0, 1, or 2.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.