Rotting Oranges
The key idea
Every rotten orange spreads at the same time, so model it as a multi-source BFS: seed the queue with all initially rotten oranges at once and expand level by level. Each BFS level is one minute. Track the count of fresh oranges; if any remain after the spread stops, return
-1.Problem
You are given an m x n grid where each cell can have one of three values: 0 for an empty cell, 1 for a fresh orange, or 2 for a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
Constraints
m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j]is0,1, or2
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
Input: grid = [[0,2]]
Output: 0
Complexity
Time: O(m*n) Space: O(m*n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More BFS / DFS problems
- 01 MatrixMEDIUM
- Average of Levels in Binary TreeEASY
- Binary Tree Level Order TraversalMEDIUM
- Binary Tree Level Order Traversal IIMEDIUM
- Binary Tree Right Side ViewMEDIUM
- Binary Tree Zigzag Level Order TraversalMEDIUM
- Find Bottom Left Tree ValueMEDIUM
- Find Largest Value in Each Tree RowMEDIUM
- Flood FillEASY
- Keys and RoomsMEDIUM
- Max Area of IslandMEDIUM
- Maximum Level Sum of a Binary TreeMEDIUM