In a grid, 0 is empty, 1 is a fresh orange, and 2 is a rotten orange. Every minute, each rotten orange rots its fresh neighbours up, down, left and right. Return the minutes until no fresh orange is left, or minus 1 if that never happens.
DSA Animator › DSA Revision › Graph › Rotting Oranges
Remember: many starting points at once means multi source BFS. One BFS level equals one unit of time. The video solves Rotting Oranges (LeetCode 994, Medium) with the Multi-Source BFS pattern from the Graph topic, and you can replay every step in the interactive Rotting Oranges animation.
In a grid, 0 is empty, 1 is a fresh orange, and 2 is a rotten orange. Every minute, each rotten orange rots its fresh neighbours up, down, left and right. Return the minutes until no fresh orange is left, or minus 1 if that never happens.
For the grid 2 1 1, 1 1 0, 0 1 1, the answer is 4 minutes.
You could rescan the whole grid every minute, looking for oranges next to rotten ones. That repeats a lot of work, up to O of rows times columns per minute.
All rotten oranges start spreading at the same time. So put every rotten orange into the queue at the start, which is a multi source BFS. Process the queue one level at a time, and each level is one minute. Count the fresh oranges first, and decrease the count whenever one rots. If fresh oranges remain at the end, some were unreachable, so return minus 1.
At the start, only the top left orange is rotten, and there are 6 fresh ones. Minute 1: it rots its right and bottom neighbours. Minute 2: those two rot the centre and the top right orange. Minute 3: the centre rots the orange below it. Minute 4: that one rots the bottom right orange. No fresh orange is left, so the answer is 4.
In code, scan the grid once, adding rotten cells to the queue and counting fresh ones. While the queue is not empty and fresh is more than 0, process one level. For each cell in the level, rot every fresh neighbour, decrease fresh, and enqueue it. After each level, add one minute. Return minutes if fresh is 0, otherwise minus 1, in O of rows times columns.
Remember: many starting points at once means multi source BFS. One BFS level equals one unit of time.