Rotting Oranges Leetcode Problem 994 [Python Solution]
Welcome to another Python problem-solving session.
In this post, we're going to tackle the Rotting Oranges problem from LeetCode.
This problem falls under the category of Graphs and is of medium difficulty.
So, let's dive into this intriguing problem, optimize the solution for efficiency, and explore the underlying algorithm.
If you want to follow along or try the problem yourself, you can find it on LeetCode here: Rotting Oranges – LeetCode Problem 994.
Problem Overview
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.
- 2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Your task is to return the minimum number of minutes that must elapse until no cell has a fresh orange.
If it is impossible to make all the fresh oranges rotten, return -1. To illustrate the problem, consider the following examples:
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
Example 3:
Input: grid = [[0,2]]
Output: 0
In Example 1, it takes 4 minutes to make all oranges rotten.
In Example 2, it's impossible to make all fresh oranges rotten, so the result is -1. In Example 3, there are no fresh oranges from the beginning, so the answer is 0. Now, let's understand the constraints and dive into an efficient Python solution.
Understanding Constraints
The problem's constraints are as follows:
m == grid.length: The number of rows in the grid.n == grid[i].length: The number of columns in each row.1 <= m, n <= 10: The grid size is between 1×1 and 10×10.grid[i][j]can be 0, 1, or 2: Each cell can be empty (0), a fresh orange (1), or a rotten orange (2).
Rotting Oranges LeetCode Problem Solution
Bruteforce Approach
To solve this problem efficiently, we'll use a Breadth-First Search (BFS) algorithm to simulate the rotting process.
We will start with multiple sources (initial rotten oranges) and gradually move to their adjacent fresh oranges, updating their status to rotten.
Let's take a look at the Python solution:
import collections
from typing import List
class Solution:
def orangesRotting(self, grid: List[List[int]) -> int:
q = collections.deque()
fresh = 0
time = 0
for r in range(len(grid)):
for c in range(len(grid[0])):
if grid[r][c] == 1:
fresh += 1
if grid[r][c] == 2:
q.append((r, c))
directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
while fresh > 0 and q:
length = len(q)
for i in range(length):
r, c = q.popleft()
for dr, dc in directions:
row, col = r + dr, c + dc
if (
row in range(len(grid))
and col in range(len(grid[0]))
and grid[row][col] == 1
):
grid[row][col] = 2
q.append((row, col))
fresh -= 1
time += 1
return time if fresh == 0 else -1
Efficient Approach with BFS
In the efficient solution, we start by initializing a queue (q) to store the positions of rotten oranges, variables for tracking fresh oranges, and time.
We iterate through the grid to identify fresh and rotten oranges, updating our variables accordingly.
We use a directions array to represent the four possible adjacent spots.
Then, we enter a loop that simulates the rotting process.
For each minute, we process the oranges currently in the queue, making their adjacent fresh oranges rotten.
We keep track of time and decrement the count of fresh oranges.
We continue this process until there are no fresh oranges left or the queue becomes empty.
At the end of the loop, we return the elapsed time if there are no fresh oranges left, indicating success, or -1 if some oranges remain fresh.
Time and Space Complexity
The time complexity of this solution is O(m * n), where m and n are the dimensions of the grid.
In the worst case, we visit each cell once.
The space complexity is also O(m * n) due to the queue used to store the positions of rotten oranges.
Reasoning Behind Our Efficient Approach
The efficient approach uses a Breadth-First Search (BFS) algorithm to simulate the rotting process.
BFS is ideal for this problem because it efficiently explores multiple sources (initial rotten oranges) and propagates the rotting effect to their adjacent fresh oranges in a controlled manner.
We start with multiple initial rotten oranges and use a queue to keep track of the current state.
In each iteration, we process the oranges in the queue, making their adjacent fresh oranges rotten and updating the count of fresh oranges.
This continues until all fresh oranges are rotten or no further rotting is possible.
The BFS algorithm ensures that we explore the grid efficiently and minimizes the time complexity.
This approach is both intuitive and efficient for solving the problem.
Related Interview Questions By Company:
Related Interview Questions By Difficulty:
- Number Of Connected Components In An Undirected Graph LeetCode
- Open The Lock LeetCode
- Surrounded Regions LeetCode
Related Interview Questions By Category:
Conclusion
In this blog post, we tackled the Rotting Oranges problem from LeetCode, optimizing the solution for efficiency.
We used a Breadth-First Search (BFS) algorithm to simulate the rotting process, starting with multiple initial rotten oranges and gradually making adjacent fresh oranges rotten.
The problem was analyzed, and the solution was explained in detail.
If you found this post helpful and want to explore more problems and solutions, don't forget to like and engage.
Your support is highly appreciated.
If you have questions, suggestions, or want to share your thoughts, please feel free to comment.
Sharing knowledge and insights is what makes the programming community thrive.
Happy coding!
