Rotting Oranges | Leetcode 994 | Explained

Learn how to solve the “Rotting Oranges” problem from LeetCode using a breadth-first search (BFS) approach. We walk through the code step by step, explain the logic in plain English, and analyze time and space complexity.

What the Problem Asks

LeetCode 994: Rotting Oranges
You’re given a 2D grid where:

• 0 = empty cell
• 1 = fresh orange
• 2 = rotten orange

Every minute, any fresh orange adjacent (up, down, left, right) to a rotten one becomes rotten.
Return the minimum number of minutes until no fresh oranges remain. If some fresh oranges can never rot, return -1.

1. Intuition & Approach

1. BFS:
   • All initially rotten oranges rot neighbors in parallel.
   • We treat each rotten orange as a starting point in our BFS queue.
2. Track Fresh Count and Time:
   • Count all fresh oranges at the start.
   • Each BFS “layer” represents one minute passing.
   • When we rot neighbors, we decrement the fresh count.
3. End Conditions:
   • If after BFS we still have fresh oranges, return -1.
   • Otherwise, return the minutes elapsed.

2. Code Implementation

from copy import deepcopy
from collections import deque
from typing import List


class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        grid_copy = deepcopy(grid)

        fresh_cnt = 0
        queue = deque()

        for r in range(rows):
            for c in range(cols):
                if grid_copy[r][c] == 2:
                    queue.append((r, c))
                elif grid_copy[r][c] == 1:
                    fresh_cnt += 1
                    
        minutes = 0
        
        while len(queue) != 0 and fresh_cnt > 0:
            minutes += 1
            total_rotten = len(queue)
            for _ in range(total_rotten):
                i, j = queue.popleft()
                for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
                    new_i, new_j = i + dx, j + dy
                    if new_i < 0 or new_i == rows or new_j < 0 or new_j == cols:
                        continue
                    if grid_copy[new_i][new_j] == 0 or grid_copy[new_i][new_j] == 2:
                        continue
                    fresh_cnt -= 1
                    grid_copy[new_i][new_j] = 2
                    queue.append((new_i, new_j))
                    
        if fresh_cnt > 0:
            return -1
        return minutes

3. Code Explanation

• Deep Copy Grid:
  We clone the grid so we don’t modify the original input.
• Initialization: pythonCopyfresh_cnt = 0 queue = deque() for each cell: if rotten (2): enqueue its coordinates if fresh (1): increment fresh_cnt This sets up all rotten oranges as BFS sources and counts how many fresh oranges we need to rot.
• BFS Loop: pythonCopywhile queue and fresh_cnt > 0: minutes += 1 for _ in range(len(queue)): i, j = queue.popleft() for each neighbor (up/down/left/right): if it’s a fresh orange: mark rotten, decrement fresh_cnt, enqueue it Each iteration of the outer while represents one minute. We process all oranges that are rotten at the start of that minute.
• Final Check: pythonCopyreturn -1 if fresh_cnt > 0 else minutes If any fresh oranges remain after the BFS, they can never rot — return -1. Otherwise, return the minutes counted.

4. Dry Run Example

Initial grid:
 2 1 1
 1 1 0
 0 1 1

• Minute 0: Rotten queue = [(0,0)], fresh_cnt = 5
• Minute 1: Rot neighbors of (0,0): (1,0) and (0,1). fresh_cnt → 3
• Minute 2: Queue = [(1,0),(0,1)] → rot their neighbors → fresh_cnt → 1
• Minute 3: Rot the last fresh at (2,1), fresh_cnt → 0
• End: All oranges rotten in 3 minutes.

5. Time & Space Complexity

• Time Complexity:
  • We visit each cell at most once → O(R·C) for an R×C grid.
• Space Complexity:
  • The queue can hold up to O(R·C) entries in the worst case.
  • We also store the grid copy → O(R·C).

6. Conclusion

Using a multi-source BFS, we simulate minute-by-minute rotting of oranges in parallel. This clear, level-by-level approach ensures we find the minimum time or detect impossibility quickly in O(R·C) time. It’s a versatile pattern for any problem where multiple starting points spread an effect in waves, think fire spread, infection modeling, or water fill problems. Happy coding!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.