Pattern 22: LeetCode Interview Patterns24 sections · 736 units
Open in Course

LeetCode 994 Rotting Oranges - Why Naive Fails

The trap

Simulate minute by minute: scan entire grid, mark oranges that should rot, update grid, repeat.

Each minute, you scan m⋅nm \cdot n cells. With up to m⋅nm \cdot n oranges, worst case O((m⋅n)2)O((m \cdot n)^2).

Can you avoid rescanning the entire grid each minute?