Rotting Oranges – Solution & Complexity
Watch: Rotting Oranges with multi-source BFS
Put every rotten orange in a queue at minute 0 and count the fresh ones. Process the queue one round at a time, so each round is one minute: rot every fresh neighbor, subtract one from fresh, and enqueue it. Loop while the queue is non-empty and fresh is above zero, or you count one extra minute. Return minutes if fresh reached zero, otherwise -1. O(rows × cols) time and space.
Solution Walkthrough
Step 1: Understand the Goal
- Identify the required output and the state that changes.
- Use the examples to rule out tempting but incorrect interpretations.
Step 2: Choose the Core Pattern
- This problem is best exposed by Multi-source BFS expands one minute-layer at a time.
- Maintain only the state needed for the next operation.
Step 3: Build the Algorithm
- Process each state once when possible.
- Record state before scheduling dependent work to avoid duplicates.
Step 4: Check Edge Cases
- Verify the smallest input, impossible cases, and repeated values where allowed.
- Keep output ordering deterministic.
Step 5: Final Solution and Complexity
- Time complexity is O(m*n).
- Space complexity is O(m*n).