Rotting Oranges: A Comprehensive Guide to Solving with BFS in Python

Introduction

In this article, we delve into solving the Rotting Oranges problem using the Breadth-First Search (BFS) algorithm in Python.

Understanding this problem not only helps in mastering BFS but also enhances problem-solving skills in grid-based challenges. Let's explore the solution step-by-step.

Problem Statement

You are given an m x n grid where each cell can have one of three values:

• 0 representing an empty cell,

• 1 representing a fresh orange, or

• 2 representing 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 this is impossible, return -1.

Example 1:

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]]
Output: 0
Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Understanding the Grid and Problem Dynamics

The grid represents a matrix where each cell's value determines its state. Fresh oranges 1 rot if they are adjacent (up, down, left, right) to a rotten orange 2. The challenge is to simulate this process and determine the time taken for all fresh oranges to rot or identify if it's impossible.

Introduction to Breadth-First Search (BFS)

Breadth-First Search (BFS) is an algorithm used for traversing or searching tree or graph data structures. It starts at a chosen node (often called the 'root') and explores all neighbor nodes at the present depth prior to moving on to nodes at the next depth level.

BFS is ideal for this problem because it processes nodes in layers, simulating the minute-by-minute rotting process effectively.

Solution Approach

Our approach involves the following steps:

1. Initialization: Identify the initial state of the grid by counting fresh oranges and adding the positions of rotten oranges to a queue.

2. BFS Traversal: Use the queue to process each rotten orange and rot adjacent fresh oranges. Track the number of minutes passed.

3. Termination: The process continues until all reachable fresh oranges are rotted. Return the total minutes or -1 if some fresh oranges cannot be rotted.

VI. Python Code Implementation

Here’s the complete Python code implementing the above approach:

from typing import List
from collections import deque

def orangesRotting(grid: List[List[int]]) -> int:
    rows, cols = len(grid), len(grid[0])
    queue = deque()
    fresh_oranges = 0

    # Initialize the queue with all the rotten oranges' positions
    # and count the number of fresh oranges.
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                queue.append((r, c))
            elif grid[r][c] == 1:
                fresh_oranges += 1

    # Directions for moving up, down, left, and right
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]

    minutes_passed = 0

    # Perform BFS
    while queue and fresh_oranges > 0:
        minutes_passed += 1
        for _ in range(len(queue)):
            x, y = queue.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                # If the adjacent cell is a fresh orange, it becomes rotten
                if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1:
                    grid[nx][ny] = 2
                    queue.append((nx, ny))
                    fresh_oranges -= 1

    # If there are still fresh oranges left, return -1
    return minutes_passed if fresh_oranges == 0 else -1

Code Explanation

Let's break down the code to understand each part:

1. Initialization:

• We define the grid dimensions (rows and cols).

• We initialize a queue to store the positions of rotten oranges and a counter for fresh oranges.

• We iterate through the grid to populate the queue with rotten oranges and count the fresh oranges.

2. BFS Traversal:

• We define the possible directions for movement (up, down, left, right).

• We initialize minutes_passed to zero.

• We perform BFS by processing each rotten orange in the queue, rotting adjacent fresh oranges, and updating the grid and queue accordingly.

• For each minute that passes, we increment the minutes_passed counter.

3. Termination:

• The loop continues until there are no more fresh oranges or the queue is empty.

• Finally, we check if there are any fresh oranges left. If not, we return the total minutes passed; otherwise, we return -1.

Time and Space Complexity Analysis

• Time Complexity: The time complexity is O(m * n) because each cell is processed at most once, and we traverse all cells in the grid.

• Space Complexity: The space complexity is also O(m * n) due to the additional storage for the queue and the grid itself.

Conclusion

Solving the Rotting Oranges problem using BFS provides a clear understanding of grid traversal and the practical application of BFS in simulating processes. This approach ensures an optimal solution with a thorough explanation of each step.

Practice similar problems to master BFS and enhance your problem-solving skills.

Related Articles

• "Mastering LeetCode's Coin Change Problem: A Comprehensive Guide"

• "Mastering LeetCode: Counting the Number of Islands in a 2D Binary Grid"

• "Mastering LeetCode: Implementing a Trie (Prefix Tree) in Python"

• "Mastering the Clone Graph Problem on LeetCode: A Comprehensive Guide"