Rotting Oranges

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    A grid holds empty cells (0), fresh oranges (1) and rotten oranges (2). Every minute, each rotten orange rots the fresh oranges directly above, below, left and right of it. Return the number of minutes until no fresh orange remains, or −1 if that never happens.

    The twist on plain BFS is that rot starts from many places at once. Putting all starting points in the queue together, a multi-source BFS, gives every cell its earliest time in one pass. Original problem: LeetCode 994.

    Example

    Starting from the rotten orange in the top-left corner, rot reaches the last fresh orange in the bottom-right after four minutes.
    Starting from the rotten orange in the top-left corner, rot reaches the last fresh orange in the bottom-right after four minutes.
    Input:  [[2,1,1],
             [1,1,0],
             [0,1,1]]
    Output: 4
    Input:  [[2,1,1],
             [0,1,1],
             [1,0,1]]
    Output: -1     # the bottom-left orange is cut off

    Constraints (assumed)

    • 1 ≤ rows, cols ≤ 10.
    • Each cell is 0, 1 or 2.

    What this question tests

    • BFS on a grid where BFS rounds equal time steps.
    • Multi-source BFS: starting from every source at once.
    • Detecting unreachable cells.

    Questions to ask first

    1. Do diagonals spread rot? (Here: no, four directions.)
    2. What if there are no fresh oranges at the start? (Answer 0.)
    3. What if there are fresh oranges but no rotten ones? (Answer −1.)
    4. Can I modify the grid? (Here: yes; otherwise copy it.)