Rotting Oranges

Medium · Graphs · Explanation and code example

Breadth First Search (No Queue)

How it works

This is still BFS by levels, but instead of using a queue, we simulate "minutes" with grid marking.

Think of each loop iteration as 1 minute:

  • Cells with value 2 are the oranges that are rotten at the start of this minute.
  • Any fresh neighbor they rot during this minute is temporarily marked as 3 (meaning "will become rotten next minute").
  • After scanning the whole grid, we convert all 3 → 2 to prepare for the next minute.

Why use 3?

  • To prevent a newly rotted orange from spreading in the same minute (which would incorrectly speed up time).

If during a minute no fresh orange becomes 3, but fresh still exists, then rot can't spread anymore → return -1.

Steps

  1. Count fresh oranges (value 1).
  2. Repeat while fresh > 0:
    • Set flag = false (did we rot anything this minute?).
    • Scan every cell:
      • If cell is 2, check 4 neighbors.
      • For each neighbor that is 1, mark it 3, decrement fresh, set flag = true.
    • If flag is false → no progress → return -1.
    • Scan again and convert all 3 to 2 (commit the next BFS layer).
    • Increment time.
  3. When fresh == 0, return time.

Complexity

  • Time complexity: O((m * n) ^ 2)
  • Space complexity: O(1)

Where m is the number of rows and n is the number of columns in the grid.

Things to watch for

Starting BFS from a Single Rotten Orange

A common mistake is initializing BFS with only one rotten orange instead of all of them simultaneously. Since all rotten oranges spread rot at the same time, you must add every cell with value 2 to the queue before starting BFS. Starting from just one source gives incorrect time calculations.

Forgetting to Track Fresh Orange Count

Some solutions forget to count fresh oranges initially and check if any remain unreachable. Without tracking the fresh count, you cannot determine whether all oranges can be rotted or if some are isolated. Always decrement fresh when an orange rots and return -1 if fresh > 0 after BFS completes.

Incrementing Time Incorrectly

A subtle bug occurs when incrementing time after processing each individual orange rather than after each BFS level. Each level represents one minute, so you must process all oranges at the current level before incrementing time. Use a loop that processes len(queue) elements per iteration to correctly track levels.

Python code example

from typing import List

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        fresh = 0
        time = 0

        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 1:
                    fresh += 1

        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]

        while fresh > 0:
            flag = False
            for r in range(ROWS):
                for c in range(COLS):
                    if grid[r][c] == 2:
                        for dr, dc in directions:
                            row, col = r + dr, c + dc
                            if (row in range(ROWS) and
                                col in range(COLS) and
                                grid[row][col] == 1):
                                grid[row][col] = 3
                                fresh -= 1
                                flag = True

            if not flag:
                return -1

            for r in range(ROWS):
                for c in range(COLS):
                    if grid[r][c] == 3:
                        grid[r][c] = 2

            time += 1

        return time

C++ code example

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int ROWS = grid.size(), COLS = grid[0].size();
        int fresh = 0, time = 0;

        for (int r = 0; r < ROWS; r++) {
            for (int c = 0; c < COLS; c++) {
                if (grid[r][c] == 1) fresh++;
            }
        }

        vector<vector<int>> directions = {{0, 1}, {0, -1},
                                          {1, 0}, {-1, 0}};

        while (fresh > 0) {
            bool flag = false;
            for (int r = 0; r < ROWS; r++) {
                for (int c = 0; c < COLS; c++) {
                    if (grid[r][c] == 2) {
                        for (auto& d : directions) {
                            int row = r + d[0], col = c + d[1];
                            if (row >= 0 && col >= 0 &&
                                row < ROWS && col < COLS &&
                                grid[row][col] == 1) {
                                grid[row][col] = 3;
                                fresh--;
                                flag = true;
                            }
                        }
                    }
                }
            }

            if (!flag) return -1;

            for (int r = 0; r < ROWS; r++) {
                for (int c = 0; c < COLS; c++) {
                    if (grid[r][c] == 3) grid[r][c] = 2;
                }
            }

            time++;
        }

        return time;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations