Problem Description

You have a grid of size m x n where each cell contains one of three possible values:

• 0: an empty cell
• 1: a fresh orange
• 2: a rotten orange

The rotting process works as follows: every minute, any fresh orange that is directly adjacent (up, down, left, or right) to a rotten orange will become rotten.

Your task is to find the minimum number of minutes needed for all fresh oranges to become rotten. If it's impossible for all fresh oranges to rot (for example, if a fresh orange is isolated and cannot be reached by any rotten orange), return -1.

For example, if you have a grid where rotten oranges are at certain positions and fresh oranges are adjacent to them, the rotting will spread minute by minute. After the first minute, all fresh oranges directly next to the initial rotten oranges become rotten. After the second minute, the newly rotten oranges from minute 1 will cause their adjacent fresh oranges to rot, and so on.

The algorithm uses BFS (Breadth-First Search) to simulate this minute-by-minute spreading process. It starts by finding all initially rotten oranges and counting all fresh oranges. Then it processes the rotting in rounds, where each round represents one minute. In each round, all currently rotten oranges spread the rot to their adjacent fresh oranges simultaneously. The process continues until either all fresh oranges have rotted (return the number of minutes elapsed) or no more fresh oranges can be reached (return -1).

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The grid can be viewed as a graph where each cell is a node, and edges connect to 4-directionally adjacent cells. The rotting process spreads from rotten oranges to fresh ones through these connections.

Is it a tree?

• No: The grid structure has multiple paths between cells and can contain cycles, so it's not a tree.

Is the problem related to directed acyclic graphs?

• No: The grid allows bidirectional movement between adjacent cells, and the problem isn't about directed relationships.

Is the problem related to shortest paths?

• Yes: We need to find the minimum time (shortest path in terms of steps) for the rot to spread from all rotten oranges to all fresh oranges.

Is the graph Weighted?

• No: Each step of spreading takes exactly 1 minute, so all edges have the same weight (unweighted graph).

BFS

• Yes: Since we have an unweighted shortest path problem, BFS is the appropriate algorithm.

Conclusion: The flowchart suggests using BFS (Breadth-First Search) for this problem. BFS is perfect here because:

1. We need to simulate the simultaneous spreading from multiple sources (all initially rotten oranges)
2. Each level of BFS represents one minute of time
3. BFS guarantees we find the minimum time needed since it explores all cells at distance k before exploring cells at distance k+1

Intuition

The key insight is to think of the rotting process as waves spreading outward from multiple sources simultaneously. Imagine dropping multiple stones into a pond at the same time - the ripples expand outward from each stone, and where they meet, they've both reached that point at the same time.

In our problem, the rotten oranges are like those stones, and the rotting process spreads like ripples. Each "wave" or "ripple" represents one minute of time. All oranges at distance 1 from any rotten orange will rot after 1 minute, all oranges at distance 2 will rot after 2 minutes, and so on.

This naturally leads us to BFS because:

1. BFS processes nodes level by level, which perfectly models the minute-by-minute spreading
2. We can start with all initially rotten oranges in our queue (multiple starting points)
3. Each level of BFS represents one unit of time

The algorithm maintains a counter cnt for fresh oranges. As we process each level:

• We rot all reachable fresh oranges at the current distance
• We decrement cnt for each newly rotten orange
• We track how many levels (minutes) we've processed

The beauty of this approach is that BFS guarantees we're always rotting oranges in the optimal order - closest ones first. When cnt reaches 0, we know all fresh oranges have rotted, and the number of levels processed equals the minimum time needed.

If after BFS completes, cnt > 0, it means some fresh oranges were unreachable (isolated), so we return -1.

Learn more about Breadth-First Search patterns.

Solution Approach

The implementation follows a standard BFS pattern with some preprocessing:

Step 1: Initial Setup and Counting First, we traverse the entire grid once to:

• Find all initially rotten oranges (value 2) and add their coordinates (i, j) to a queue q
• Count all fresh oranges (value 1) and store in variable cnt
• This preprocessing helps us know our starting points and when to stop

Step 2: BFS Initialization

• Initialize ans = 0 to track the number of minutes elapsed
• Define directions array dirs = (-1, 0, 1, 0, -1) for 4-directional movement
  • Using pairwise(dirs) gives us [(-1, 0), (0, 1), (1, 0), (0, -1)] representing up, right, down, left

Step 3: Level-by-Level BFS Processing The main BFS loop continues while q is not empty AND cnt > 0:

• Increment ans at the start of each level (representing one minute passing)
• Process all oranges at the current level using for _ in range(len(q)):
  • For each rotten orange (i, j), check all 4 adjacent cells
  • Calculate new coordinates: x, y = i + a, j + b
  • If the adjacent cell is within bounds and contains a fresh orange (grid[x][y] == 1):
    • Mark it as rotten: grid[x][y] = 2
    • Add it to queue for next level: q.append((x, y))
    • Decrement fresh count: cnt -= 1
    • Early termination: if cnt == 0, immediately return ans

Step 4: Final Result After BFS completes:

• If cnt > 0: Some fresh oranges couldn't be reached, return -1
• If cnt == 0: All fresh oranges have rotted, return 0 (or ans if terminated early)

The time complexity is O(m × n) where we visit each cell at most once. The space complexity is also O(m × n) in the worst case when all cells contain rotten oranges initially.

Example Walkthrough

Let me walk through a small example to illustrate how the BFS solution works.

Consider this 3×3 grid:

2 1 1
1 1 0
0 1 1

Initial Setup (Step 1):

• Scan the grid to find rotten oranges and count fresh ones
• Found rotten orange at position (0,0)
• Fresh orange count cnt = 6
• Queue q = [(0,0)]

Minute 1 (First BFS Level):

• Process position (0,0), check its 4 neighbors:
  • Up: out of bounds
  • Right: (0,1) has fresh orange → rot it, add to queue
  • Down: (1,0) has fresh orange → rot it, add to queue
  • Left: out of bounds
• Grid after minute 1:

2 2 1
2 1 0
0 1 1

• Queue for next level: [(0,1), (1,0)]
• Fresh count: cnt = 4
• Time elapsed: ans = 1

Minute 2 (Second BFS Level):

• Process (0,1):
  • Right neighbor (0,2) has fresh orange → rot it
  • Down neighbor (1,1) has fresh orange → rot it
• Process (1,0):
  • Right neighbor (1,1) already being rotted this round
  • Down neighbor (2,0) is empty, skip
• Grid after minute 2:

2 2 2
2 2 0
0 1 1

• Queue for next level: [(0,2), (1,1)]
• Fresh count: cnt = 2
• Time elapsed: ans = 2

Minute 3 (Third BFS Level):

• Process (0,2):
  • No fresh neighbors
• Process (1,1):
  • Down neighbor (2,1) has fresh orange → rot it
• Grid after minute 3:

2 2 2
2 2 0
0 2 1

• Queue for next level: [(2,1)]
• Fresh count: cnt = 1
• Time elapsed: ans = 3

Minute 4 (Fourth BFS Level):

• Process (2,1):
  • Right neighbor (2,2) has fresh orange → rot it
• Grid after minute 4:

2 2 2
2 2 0
0 2 2

• Fresh count: cnt = 0 → All oranges are rotten!
• Return ans = 4

The algorithm correctly determines that it takes 4 minutes for all fresh oranges to rot, with the rotting spreading outward level by level from the initial rotten orange at the top-left corner.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n)

The algorithm performs a BFS traversal starting from all initially rotten oranges. In the worst case, every cell in the grid needs to be visited exactly once. The initial scan to find all rotten oranges and count fresh oranges takes O(m × n) time. The BFS process visits each cell at most once, as each fresh orange becomes rotten exactly once and is added to the queue once. Therefore, the total time complexity is O(m × n).

Space Complexity: O(m × n)

The space complexity is determined by the queue used for BFS. In the worst-case scenario, all oranges could be rotten initially (all cells contain 2), which means the queue would need to store all m × n positions at the start. Even in a more typical case where oranges rot progressively, the queue could potentially hold O(m × n) elements at any given time (for example, when a wave of rotting spreads across a large portion of the grid simultaneously). Therefore, the space complexity is O(m × n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Minute Counting Logic

A common mistake is incrementing minutes_elapsed at the wrong time or returning the wrong value when all oranges are already rotten initially.

Pitfall Example:

# WRONG: This increments time even when no fresh oranges exist
while queue:
    minutes_elapsed += 1
    # ... BFS logic
return minutes_elapsed

Why it's wrong: If the grid has only rotten oranges (no fresh oranges), this would return a non-zero value when it should return 0.

Correct Approach:

# Only process BFS if there are fresh oranges to rot
while queue and fresh_count > 0:
    minutes_elapsed += 1
    # ... BFS logic

# Return 0 if no fresh oranges existed initially
return -1 if fresh_count > 0 else 0

2. Not Processing Level-by-Level in BFS

Pitfall Example:

# WRONG: Processing oranges one by one instead of level by level
while queue and fresh_count > 0:
    curr_row, curr_col = queue.popleft()
    for row_delta, col_delta in directions:
        # ... rot adjacent oranges
    minutes_elapsed += 1  # Wrong! This counts each orange as a minute

Why it's wrong: Each minute, ALL currently rotten oranges should spread rot simultaneously. Processing them one-by-one would count each orange as a separate minute.

Correct Approach:

while queue and fresh_count > 0:
    minutes_elapsed += 1
    current_level_size = len(queue)  # Capture current level size
    for _ in range(current_level_size):  # Process entire level
        curr_row, curr_col = queue.popleft()
        # ... rot adjacent oranges

3. Forgetting Edge Cases

Common scenarios to handle:

• Empty grid or grid with all empty cells (should return 0)
• Grid with only fresh oranges and no rotten ones (should return -1)
• Grid with only rotten oranges (should return 0)
• Single cell grids

Solution: Always check fresh_count before and after BFS:

# After initial scan
if fresh_count == 0:
    return 0  # No fresh oranges to rot

# After BFS
return -1 if fresh_count > 0 else minutes_elapsed

4. Modifying Grid Without Checking Bounds First

Pitfall Example:

# WRONG: Accessing grid before bounds check
for row_delta, col_delta in directions:
    next_row = curr_row + row_delta
    next_col = curr_col + col_delta
    if grid[next_row][next_col] == 1:  # IndexError possible!
        if 0 <= next_row < rows and 0 <= next_col < cols:
            # ...

Correct Approach: Always check bounds before accessing grid:

if (0 <= next_row < rows and 
    0 <= next_col < cols and 
    grid[next_row][next_col] == 1):
    # Safe to access and modify