Graph Theory37 sections · 1633 units
Open in Course

LeetCode 994 Rotting Oranges - Problem Statement

LeetCode 994

You have a grid where each cell contains a fresh orange (value 11), a rotten orange (value 22), or is empty (value 00). Every minute, any fresh orange adjacent to a rotten orange (up, down, left, right) becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return 1-1.

This is multi-source BFS. You start from all rotten oranges at once, not from a single source. Each rotten orange spreads rot in parallel. Before reading on, think: how would you track time? What makes this different from single-source BFS?