How do you solve Rotting Oranges on LeetCode?

Rotting Oranges (LeetCode #994) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(m * n) time complexity and O(m * n) space complexity. Key insight: BFS is effective for problems involving spreading processes, like rotting oranges.

What is the brute force solution for Rotting Oranges?

The brute force approach for Rotting Oranges is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves repeatedly checking the grid for fresh oranges and marking them as rotten if they are adjacent to any rotten oranges. This process continues until no fresh oranges are left or no more can be rotted. The optimal Optimal Solution approach improves this to O(m * n).

What algorithm or data structure is used to solve Rotting Oranges?

Rotting Oranges uses the following concepts: Array, Breadth-First Search, Matrix. The recommended patterns to study are: Breadth-First Search, Graph Traversal.

What are the interview tips for Rotting Oranges?

Clearly explain your thought process while coding. Consider edge cases before finalizing your solution. Practice BFS problems to get comfortable with queue operations.

What are common mistakes when solving Rotting Oranges?

Not considering edge cases where fresh oranges are isolated. Failing to update the grid correctly during the BFS process.

#994

Rotting Oranges

Medium

ArrayBreadth-First SearchMatrixBreadth-First SearchGraph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(m * n)
Space	O(1)	O(m * n)

💡

Intuition

Time O(m * n)Space O(m * n)

The optimal solution uses a Breadth-First Search (BFS) approach, where we explore all rotten oranges simultaneously and propagate the rotting effect to adjacent fresh oranges. This way, we can efficiently track the time taken for all fresh oranges to rot.

⚙️

Algorithm

6 steps

1Step 1: Initialize a queue and add all rotten oranges to it.
2Step 2: Initialize a variable for minutes and a counter for fresh oranges.
3Step 3: While the queue is not empty, process all rotten oranges in the queue for the current minute.
4Step 4: For each rotten orange, check its four neighbors; if a neighbor is a fresh orange, mark it as rotten and add it to the queue.
5Step 5: Increment the minute counter after processing all rotten oranges for that minute.
6Step 6: After processing, if there are still fresh oranges left, return -1; otherwise, return the minute counter.

solution.py25 lines

1# Full working Python code
2from collections import deque
3
4def orangesRotting(grid):
5    queue = deque()
6    fresh_count = 0
7    for i in range(len(grid)):
8        for j in range(len(grid[0])):
9            if grid[i][j] == 2:
10                queue.append((i, j))
11            elif grid[i][j] == 1:
12                fresh_count += 1
13    minutes = 0
14    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
15    while queue:
16        for _ in range(len(queue)):
17            x, y = queue.popleft()
18            for dx, dy in directions:
19                nx, ny = x + dx, y + dy
20                if 0 <= nx < len(grid) and 0 <= ny < len(grid[0]) and grid[nx][ny] == 1:
21                    grid[nx][ny] = 2
22                    fresh_count -= 1
23                    queue.append((nx, ny))
24        minutes += 1
25    return minutes if fresh_count == 0 else -1

ℹ

Complexity note: The time complexity is O(m * n) because we may need to visit each cell in the grid once. The space complexity is O(m * n) due to the queue that stores the positions of rotten oranges, which can grow to the size of the grid in the worst case.

1BFS is effective for problems involving spreading processes, like rotting oranges.
2Tracking the number of fresh oranges helps determine if all can be rotted.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.