Rotting Oranges in Python | BFS vs DFS Approach with Code & Comparison

Rotting Oranges in Python: DFS vs BFS Explained

The Rotting Oranges problem (LeetCode 994) is a classic grid traversal challenge. The task is to determine how many minutes it takes to rot all fresh oranges in a grid given that rotten oranges rot their neighbors in 4 directions every minute.

In this article, we will walk through two different approaches to solve this problem in Python:

• A recursive DFS approach that tracks minimum rot times
• An optimized and efficient BFS approach using a queue

---

1. DFS Approach

The DFS solution recursively spreads the “rot” from every rotten orange and uses a matrix to keep track of the minimum time taken for each orange to rot. This avoids revisiting oranges unnecessarily and ensures that only the shortest path is used.

You can find the complete code here:

DFS Solution (LC994_V1.py)

class Solution:
    def rotOranges(self, i, j, itr):

        if i < 0 or j < 0 or i >= self.m or j >= self.n or self.grid[i][j] == 0 or itr > self.answer[i][j]:
            return

        self.answer[i][j] = itr
        self.rotOranges(i+1, j, itr+1)
        self.rotOranges(i, j+1, itr+1)
        self.rotOranges(i-1, j, itr+1)
        self.rotOranges(i, j-1, itr+1)

    def orangesRotting(self, grid: List[List[int]]) -> int:
        self.grid = grid
        self.m = len(grid)
        self.n = len(grid[0])
        self.answer = []

        for i in range(self.m):
            temp = []
            for j in range(self.n):
                if self.grid[i][j] == 1:
                    temp.append(self.m*self.n)
                else:
                    temp.append(0)
            self.answer.append(temp)
        
        for i in range(self.m):
            for j in range(self.n):
                if self.grid[i][j] == 2:
                    self.rotOranges(i, j, 0)
        result = max([max(self.answer[i]) for i in range(self.m)])
        if result == self.m * self.n:
            return -1

        return result

How This Works

• Initializes a matrix to store the earliest time each orange becomes rotten.
• Recursively traverses neighbors, updating times if a faster path is found.
• Uses pruning to prevent exploring slower paths.

---

2. BFS Approach

The BFS solution treats the problem like a real-world spread: rotting happens level by level (“minute by minute”). It pushes all initially rotten oranges into a queue and expands outward in 4 directions each minute.

You can find the full implementation here:

BFS Solution (LC994_V2.py)

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

        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 1:
                    fresh += 1
                
                elif grid[r][c] == 2:
                    q.append([r, c])
                    
        directions = [[0, 1], [1, 0], [-1, 0], [0, -1]]
        while q and fresh > 0:

            for i in range(len(q)):

                r, c = q.popleft()

                for dr, dc in directions:
                    row, col = dr + r, dc + c
                    if (row<0 or col<0 or row>=ROWS or col>=COLS or grid[row][col] != 1):
                        continue
                    
                    grid[row][col] = 2
                    q.append([row, col])
                    fresh -= 1
            
            time += 1
        
        return time if fresh == 0 else -1

How This Works

• Counts all fresh oranges and stores rotten ones in a queue.
• Processes all currently rotten oranges at once (represents one minute).
• Rotten neighbors get added to the queue for the next minute.
• The process repeats until either all oranges are rotten or no more spread is possible.

---

Comparison: DFS vs BFS

Criteria	DFS Solution	BFS Solution
Concept	Recursive depth search with pruning	Level-by-level traversal using a queue
Time Complexity	Potentially high in worst case	O(m × n)
Space Complexity	Recursion stack + grid memory	Queue + grid memory
Matches Problem Intuition	Indirect (distance tracking)	Direct (simulates time)
Recommended	Educational	Best for interviews & performance

---

Final Thoughts

Both approaches correctly solve the problem and help deepen your understanding of graph/grid traversals.

However, the BFS approach aligns directly with the real-world simulation of oranges rotting over time and offers better performance guarantees.

If you’re preparing for interviews, the BFS solution is highly recommended!