Rotting Oranges

📋

Problem

Imagine a warehouse full of fresh oranges where some start rotting. The rot spreads every minute to adjacent fresh oranges. How long until all oranges rot or determine if some remain fresh forever?

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 adjacent (4-directionally) 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.

1 ≤ m, n ≤ 10^2grid[i][j] is 0, 1, or 2

Edge cases: Grid with no fresh oranges → output 0Grid with no rotten oranges but fresh oranges present → output -1Grid with all empty cells → output 0

</>

IDE

def orangesRotting(grid: list[list[int]]) -> int:public int orangesRotting(int[][] grid)int orangesRotting(vector<vector<int>>& grid)function orangesRotting(grid)

def orangesRotting(grid):
    # Write your solution here
    pass

class Solution {
    public int orangesRotting(int[][] grid) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int orangesRotting(vector<vector<int>>& grid) {
    // Write your solution here
    return 0;
}

function orangesRotting(grid) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Returning 0 when fresh oranges exist but no rotten oranges to start rot.✅ Check if rotten oranges count is zero and fresh oranges count > 0; return -1 in that case.

Wrong: Less than actual minutesUsing greedy approach that rots only one orange per minute instead of all adjacent fresh oranges simultaneously.✅ Use multi-source BFS with a queue to rot all adjacent fresh oranges in the same minute before incrementing time.

Wrong: Positive number instead of -1Not checking if fresh oranges remain unreachable after BFS completes.✅ After BFS, scan grid for any fresh oranges; if found, return -1.

Wrong: Non-zero for empty gridNot handling grids with no fresh oranges correctly, incrementing time unnecessarily.✅ Return 0 immediately if no fresh oranges present before BFS.

Wrong: TLERepeatedly scanning entire grid each minute instead of BFS queue approach.✅ Implement multi-source BFS using a queue to process rotten oranges efficiently.

✓

Test Cases

Focus on handling grids with no fresh or rotten oranges and single cell grids.

Watch out for unreachable fresh oranges and greedy approaches that rot oranges one by one.

Optimize your BFS to run in O(m*n) time using a queue and multi-source initialization.

t1_01basic

Input{"grid":[[2,1,1],[1,1,0],[0,1,1]]}

Expected4

⏱ Performance - must finish in 2000ms

Rot spreads from the initial rotten orange at (0,0) to all fresh oranges in 4 minutes.

💡 Consider using BFS starting from all rotten oranges simultaneously.

💡 Use a queue to track rotten oranges and process neighbors minute by minute.

💡 Return the time after all reachable fresh oranges rot; if some remain fresh, return -1.

Why it failed: Incorrect output means BFS or time tracking is wrong; ensure you process all rotten oranges per minute and update fresh oranges correctly.

✓ Correct BFS multi-source traversal and time simulation implemented.

t1_02basic

Input{"grid":[[2,1,1],[0,1,1],[1,0,1]]}

Expected-1

⏱ Performance - must finish in 2000ms

Rot starts at (0,0) and takes 5 minutes to rot all reachable fresh oranges.

💡 Track the spread of rot carefully through all adjacent fresh oranges.

💡 Remember to check all four directions and update the grid each minute.

💡 If some fresh oranges are unreachable, return -1; here all are reachable so count minutes.

Why it failed: If output is less than 5, BFS likely missed some oranges or time increments incorrectly; fix by ensuring all neighbors are processed each minute.

✓ Correctly simulates rot spread and counts total minutes until all fresh oranges rot.

t2_01edge

Input{"grid":[[0,0,0],[0,0,0],[0,0,0]]}

Expected0

⏱ Performance - must finish in 2000ms

Grid has no fresh or rotten oranges; no time needed.

💡 Check if there are any fresh oranges at all before processing.

💡 If none, return 0 immediately as no rotting needed.

💡 Empty cells do not affect the result; rot cannot spread.

Why it failed: Returning non-zero means code does not handle empty or no fresh orange grids; fix by checking fresh count before BFS.

✓ Correctly returns 0 when no fresh oranges present.

t2_02edge

Input{"grid":[[1]]}

Expected-1

⏱ Performance - must finish in 2000ms

Single fresh orange with no rotten orange to start rot; impossible to rot.

💡 If no rotten oranges initially, fresh oranges cannot rot.

💡 Return -1 if fresh oranges remain after BFS or if BFS never starts.

💡 Check initial counts of fresh and rotten oranges before simulation.

Why it failed: Returning 0 or positive means code ignores initial rotten absence; fix by verifying rotten count before BFS.

✓ Correctly returns -1 when fresh oranges cannot rot due to no rotten oranges.

t2_03edge

Input{"grid":[[2]]}

Expected0

⏱ Performance - must finish in 2000ms

Single rotten orange, no fresh oranges to rot; time is zero.

💡 If no fresh oranges present, return 0 immediately.

💡 Initial rotten oranges do not increase time if no fresh to infect.

💡 Check fresh count before BFS to avoid unnecessary processing.

Why it failed: Returning non-zero means code incorrectly increments time even when no fresh oranges exist; fix by checking fresh count upfront.

✓ Correctly returns 0 when only rotten oranges present.

t3_01corner

Input{"grid":[[2,1,1],[0,1,0],[1,0,1]]}

Expected-1

⏱ Performance - must finish in 2000ms

Some fresh oranges are isolated by empty cells and cannot be rotted; result is -1.

💡 Check connectivity carefully; BFS cannot reach isolated fresh oranges.

💡 If any fresh orange remains after BFS, return -1.

💡 Ensure BFS processes all rotten oranges and their reachable neighbors.

Why it failed: Returning a positive number means code ignores unreachable fresh oranges; fix by verifying fresh count after BFS completes.

✓ Correctly identifies unreachable fresh oranges and returns -1.

t3_02corner

Input{"grid":[[1,1,1],[1,2,1],[1,1,1]]}

Expected8

⏱ Performance - must finish in 2000ms

Rot spreads from center rotten orange to all fresh oranges in 2 minutes.

💡 Ensure BFS spreads rot simultaneously from all rotten oranges each minute.

💡 Avoid greedy approach that rots only one orange per minute.

💡 Use multi-source BFS to simulate parallel rot spread.

Why it failed: Output less than 2 means greedy approach rotting one orange at a time; fix by using queue to rot all neighbors simultaneously each minute.

✓ Correctly simulates parallel rot spread using multi-source BFS.

t3_03corner

Input{"grid":[[2,1,0,2,1]]}

Expected1

⏱ Performance - must finish in 2000ms

Rot spreads from two rotten oranges on the same row to adjacent fresh oranges in 1 minute.

💡 Handle multiple rotten sources correctly in BFS initialization.

💡 Process all rotten oranges in the queue each minute before incrementing time.

💡 Check all four directions for each rotten orange.

Why it failed: Output greater than 1 means code processes rotten oranges sequentially instead of simultaneously; fix by initializing BFS queue with all rotten oranges at start.

✓ Correctly handles multiple rotten sources spreading rot simultaneously.

t4_01performance

Input{"_description":"n=100 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

Grid size 100x100; O(m*n) BFS must complete within 2 seconds.

💡 Use multi-source BFS with queue for efficient traversal.

💡 Avoid repeated scanning of entire grid each minute.

💡 Precompute initial rotten oranges and track fresh count.

Why it failed: TLE indicates brute force or repeated full scans per minute; fix by implementing multi-source BFS with queue.

✓ Efficient BFS completes within time limit.

Practice

1. You are given a grid of heights and need to find a path from the top-left to the bottom-right cell such that the maximum absolute difference in heights between adjacent cells on the path is minimized. Which algorithmic approach guarantees finding the optimal solution efficiently?

easy

A. Dijkstra's algorithm variant treating edge weights as the maximum effort along the path

B. Greedy algorithm that always moves to the adjacent cell with the smallest height difference

C. Dynamic programming that sums all height differences along paths

D. Depth-first search with backtracking exploring all paths exhaustively

Solution

1. Step 1: Understand the problem's cost metric

   The cost to minimize is the maximum edge effort along the path, not the sum of efforts.

2. Step 2: Identify suitable algorithm

   Dijkstra's algorithm can be adapted to track the maximum edge cost on paths, guaranteeing the minimal maximum effort path.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Dijkstra's variant correctly handles max edge cost minimization [OK]

Hint: Minimize max edge cost -> Dijkstra variant [OK]

Common Mistakes:

• Assuming greedy local choice leads to global optimum
• Using sum of efforts instead of max
• Exhaustive DFS is too slow

2. Consider the following buggy code for finding the cheapest flight within K stops. Which line contains the subtle bug that can cause incorrect results?

from collections import defaultdict
import heapq

def findCheapestPrice(n, flights, src, dst, K):
    graph = defaultdict(list)
    for u, v, w in flights:
        graph[u].append((v, w))
    heap = [(0, src, 0)]  # cost, node, stops
    while heap:
        cost, node, stops = heapq.heappop(heap)
        if node == dst:
            return cost
        if stops < K:  # BUG: should be stops <= K
            for nei, price in graph[node]:
                heapq.heappush(heap, (cost + price, nei, stops + 1))
    return -1

medium

A. Line with condition if stops < K:

B. Line initializing the heap with (0, src, 0)

C. Line checking if node == dst

D. Line pushing neighbors into the heap

Solution

1. Step 1: Understand stops constraint

   The problem allows up to K stops, meaning stops can be equal to K, not strictly less.

2. Step 2: Identify bug

   The condition 'if stops < K:' excludes paths with exactly K stops, missing valid solutions.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing to 'stops <= K' fixes the bug [OK]

Hint: Stops ≤ K allows exactly K stops, not less [OK]

Common Mistakes:

• Using stops < K instead of stops <= K
• Ignoring stops count in pruning
• Returning early without checking stops

3. What is the time complexity of the optimal Kahn's Algorithm solution for the Course Schedule problem, given V courses and E prerequisite pairs?

medium

A. O(V + E) because each node and edge is processed once in BFS

B. O(V * E) due to nested loops over nodes and edges

C. O(V^2) because each node might be checked against all others

D. O(E) only, since edges dominate the processing time

Solution

1. Step 1: Identify operations on nodes and edges

   Each node is enqueued and dequeued once; each edge is visited once when decrementing in-degree.

2. Step 2: Combine to get total complexity

   Total time is proportional to number of nodes plus number of edges -> O(V + E).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Standard BFS topological sort runs in linear time relative to graph size [OK]

Hint: Each edge and node processed once -> O(V + E) [OK]

Common Mistakes:

• Assuming nested loops cause O(V*E)
• Confusing dense graph worst case with typical complexity
• Ignoring that BFS processes nodes once

4. Consider the following buggy code snippet from the BFS approach for Pacific Atlantic Water Flow. Which line contains the subtle bug that can cause incorrect results?

medium

A. Line that appends (0, j) to pacific_queue

B. Missing line that sets atlantic_reachable[m-1][j] = True

C. Line that sets pacific_reachable[0][j] = True

D. Line that appends (m-1, j) to atlantic_queue

Solution

1. Step 1: Check border initialization

   Both oceans' reachable arrays must mark all border cells as True initially.

2. Step 2: Identify missing marking

   For atlantic ocean, bottom row cells (m-1, j) are added to queue but not marked reachable, causing BFS to miss them.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing atlantic_reachable[m-1][j] = True causes incomplete results [OK]

Hint: All border cells must be marked reachable initially [OK]

Common Mistakes:

• Forgetting to mark atlantic_reachable bottom row
• Marking visited after BFS causes infinite loops

5. Suppose the problem is modified so that diagonal neighbors (top-left, top-right, bottom-left, bottom-right) are also considered connected. Which of the following changes to the BFS algorithm correctly adapts to this new requirement without double counting or missing cells?

hard

A. Add diagonal neighbors to the neighbor list and keep the rest of the BFS code unchanged

B. Use DFS instead of BFS because BFS cannot handle diagonal connections

C. Keep neighbor list unchanged but run BFS twice, once for horizontal/vertical and once for diagonals

D. Add diagonal neighbors to the neighbor list and also mark visited cells immediately when enqueuing them

Solution

1. Step 1: Add diagonal neighbors to the neighbor list

   Include all 8 directions: horizontal, vertical, and diagonal neighbors.

2. Step 2: Mark cells as visited when enqueuing

   This prevents adding the same cell multiple times from different neighbors, avoiding double counting.

3. Step 3: Keep BFS traversal logic unchanged otherwise

   Running BFS twice or switching to DFS is unnecessary and inefficient.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Mark visited on enqueue avoids duplicates with expanded neighbors [OK]

Hint: Mark visited on enqueue when neighbors increase [OK]

Common Mistakes:

• Not marking visited on enqueue causing duplicates
• Running BFS multiple times unnecessarily
• Thinking BFS can't handle diagonals