Rotting Oranges – LeetCode75 Python Solution Explained

The Rotting Oranges problem (LeetCode75) is a grid-based BFS problem that tests your understanding of breadth-first traversal, queue management, and multi-source BFS. It is a common interview question because it evaluates your ability to simulate a spreading process efficiently in a 2D grid.

In this blog, we will break down the problem, provide examples, explain the Python solution step by step, analyze time and space complexity, discuss edge cases and explore real-world applications.

Problem Statement

You are given an m x n grid where:

• 0 represents an empty cell.
• 1 represents a fresh orange.
• 2 represents a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

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

Example 1

Input:

grid = [[2,1,1],
        [1,1,0],
        [0,1,1]]

Output:

4

Explanation:

• Minute 0: Initial rotten oranges = [0,0].
• Minute 1-4: Fresh oranges adjacent to rotten ones rot gradually.

Example 2

Input:

grid = [[2,1,1],
        [0,1,1],
        [1,0,1]]

Output:

-1

Explanation:

• Some fresh oranges cannot be reached by rotten ones.

Example 3

Input:

grid = [[0,2]]

Output:

0

• No fresh oranges present initially.

Complete Python Solution

from collections import deque
from typing import List

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 4-directional neighbors

        # Helper function to check if a position is valid and has a fresh orange
        def is_valid(i, j):
            return 0 <= i < rows and 0 <= j < cols and grid[i][j] == 1

        # Initialize the queue with the initial rotten oranges
        queue = deque()
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 2:
                    queue.append((i, j, 0))  # (row, col, minutes)

        minutes_elapsed = 0

        while queue:
            i, j, minutes_elapsed = queue.popleft()

            for di, dj in directions:
                ni, nj = i + di, j + dj
                if is_valid(ni, nj):
                    grid[ni][nj] = 2  # Mark the fresh orange as rotten
                    queue.append((ni, nj, minutes_elapsed + 1))

        # Check if there are any remaining fresh oranges
        for row in grid:
            if 1 in row:
                return -1

        return minutes_elapsed

Step-by-Step Explanation

Step 1: Initialize BFS

We first identify all initially rotten oranges and add them to a queue, marking them as starting points for BFS.

queue = deque()
for i in range(rows):
    for j in range(cols):
        if grid[i][j] == 2:
            queue.append((i, j, 0))  # row, col, minutes

Step 2: Define Directions

We define 4 possible directions for adjacency: up, down, left, right.

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

Step 3: Perform BFS

Pop each rotten orange from the queue and spread rot to adjacent fresh oranges, incrementing the minute count.

while queue:
    i, j, minutes_elapsed = queue.popleft()

    for di, dj in directions:
        ni, nj = i + di, j + dj
        if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == 1:
            grid[ni][nj] = 2
            queue.append((ni, nj, minutes_elapsed + 1))

Step 4: Check Remaining Fresh Oranges

After BFS, check if any fresh oranges remain. If yes, return -1.

for row in grid:
    if 1 in row:
        return -1

• Otherwise, return minutes elapsed.

Time and Space Complexity

• Time Complexity:O(m * n)
  • Each cell is processed at most once.
• Space Complexity:O(m * n)
  • BFS queue can store all rotten oranges.

Edge Cases

1. No fresh oranges initially: Return 0.
2. Impossible to rot all oranges: Return -1.
3. Single row or column grid: Works with BFS in any direction.
4. All oranges already rotten: Return 0.

Real-World Applications

• Epidemiology: Simulating the spread of infection in a population.
• Fire Spread Modeling: Modeling spread through connected grids.
• Network Failure Analysis: Simulating failure propagation in networks.
• Game Development: Propagation effects in 2D tile-based games.

Conclusion

The Rotting Oranges problem is an excellent BFS exercise for multi-source propagation in 2D grids. By simultaneously processing all initially rotten oranges, BFS guarantees the shortest time to rot all reachable oranges.

This problem helps improve skills in grid traversal, queue management, and simulation of spreading processes which are highly relevant for coding interviews and real-world simulations.

Related Reads

• Delete Node in a Binary Search Tree – LeetCode75 Python Solution Explained
• Number of Provinces – LeetCode75 Python Solution Explained
• Binary Tree Right Side View – LeetCode75 Python Solution Explained
• Leaf-Similar Trees – LeetCode75 Python Solution Explained
• Lowest Common Ancestor of a Binary Tree – LeetCode75 Python Solution Explained

References

1. LeetCode – Rotting Oranges
2. Breadth-First Search – GeeksforGeeks