Rotting Oranges

Medium· Multi-source BFS· Grid

Problem

In a grid, 0 is empty, 1 is a fresh orange and 2 is a rotten orange. Each minute, every fresh orange adjacent (4-directionally) to a rotten one becomes rotten. Return the minutes until no fresh orange remains, or -1 if some can never rot.

Examples

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]

Output: 4

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]

Output: -1

The orange at the bottom-left is walled off by empty cells.

Constraints

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

Hints & approach

Hint 1

Rot spreads from all rotten oranges at the same time.

Hint 2

Multi-source BFS: put every initially rotten orange in the queue together.

Hint 3

Each BFS layer is one minute; count fresh oranges to detect the -1 case.

Approachtry the hints first

Enqueue every rotten cell and count fresh ones. Process the queue one layer at a time; for each cell, rot its fresh neighbours, decrement the fresh count, and enqueue them. Increment the minute counter after each layer that is processed while fresh oranges remain. At the end, return the minutes if the fresh count is 0, otherwise -1.

Time O(m * n) · Space O(m * n)

← PreviousNumber of Islands Next →Course Schedule