Skip to content

Latest commit

 

History

History
6 lines (5 loc) · 442 Bytes

File metadata and controls

6 lines (5 loc) · 442 Bytes

bfs

From each of the rotten oranges, we can traverse to all the reachable oranges from the start. Each level is a time count.
To check whether all the fresh oranges become rotten, we can first count the number of fresh oranges, when the orange is rotten we decrease the count. When the BFS if finished we can check the number of fresh oranges left.

time: O(|E| + |V|) -> O(4 * m * n + m * n) -> O(m * n)
space: O(|V|) -> O(m + n)