Graphs & Networks
Grid BFS
When you see it
Signal words
If the prompt uses any of these, this pattern should come to mind first.
matrixgridshortest pathnearest cellrotten orangeswalls
Practice
Drill this pattern with an AI trainer — reply only with Hint, Next, Lost, or paste your code.
Ask yourself
- Is the graph implicit in four or eight grid directions?
- Do you need minimum steps from one or many sources?
- Can you mark cells as visited when enqueued?
Classic problem
Rotting Oranges (LeetCode 994) — 2 is rotten, 1 is fresh, 0 is empty. Each
minute rot spreads to adjacent fresh oranges. Return minutes until none are fresh, or -1.
Input: grid = [[2,1,1],[1,1,0],[1,0,1]]
Output: -1 — the bottom-right 1 has no rotten neighbours and can never be reached.
Common pitfalls
Using
shift()for large queues; keep a head index.
Marking visited after dequeue and adding the same cell repeatedly.