MEDIUM NC#85 Graphs / BFS
994. Rotting Oranges
📖 Problem
You are given an m x n grid where each cell has one of three values: - 0 represents an empty cell - 1 represents a fresh orange - 2 represents 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.
🧠 Visual Learning Aid
1 Model the input into the right structure
2 Choose the core technique and invariant
3 Execute step-by-step with a sample
4 Validate complexity and edge cases
JS/TS Refreshers
- •Array methods (`push`, `pop`, `shift`, `slice`)
- •Object/Map/Set usage patterns
- •Function parameter and return typing
- •Level-order traversal
- •Queue discipline
- •Shortest-step interpretation
Logical Thinking Concepts
- •Define invariants before coding
- •Check edge cases first (`[]`, single element, duplicates)
- •Estimate time/space before implementation
- •Apply BFS reasoning pattern
💡 Approach
- → Use BFS for level-by-level processing
- → Add all initially rotten oranges to queue
- → Process level by level, marking adjacent fresh oranges
- → Track minutes elapsed
- → Stop when no fresh oranges remain
- → Time: O(m * n), Space: O(m * n)
🛠️ Hints & Pitfalls
Hints
- •Use BFS for level-by-level processing
- •Add all initially rotten oranges to queue
- •Process level by level, marking adjacent fresh oranges
Common Pitfalls
- •Track minutes elapsed
- •Stop when no fresh oranges remain
- •Time: O(m * n), Space: O(m * n)
🧪 Test Cases
Hidden tests on submit: 1
Test Case 1
Not run Input:
orangesRotting([[0,2]]); Expected:
-1 Test Case 2
Not run Input:
orangesRotting(grid: number[][]); Expected:
Computed from hidden reference Test Case 3
Not run Input:
orangesRotting([
[2,1,1],
[1,1,0],
[1,0,2],
[0,2,1]
]); Expected:
Computed from hidden reference 📝 Code Editor
📤 Output