\

Rotting Oranges

Difficulty: N/A | Solved: December 20, 2025

Problem

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.

Brainstorming

Brute force attempt

On the face of it looks like a Graph traversal (wether BFS or DFS we will come to it later) problem where we are trying to check for any rotten orange if there are fresh oranges in its nearest neighbour .

  1. we need to find a rotten orange in a grid , since they can be any where
  2. then once we find them our global minute counter begins
  3. we traverse to the neighbours of the of this rotten orange , we will increment the counter of minute by 1
  4. then we explore the neighbour’s neighbours (since now they are rotten) to check for any new fresh orange in them that are now going to be rotten and then expand progressively

This however assumes that all fresh oranges are adjacent to all other oranges either fresh or rotten , which may or may not be the case , a brute force way would be to keep a count of all the fresh orange we have made rotten and i am assuming that we have a global counter for all the fresh oranges before we start the problem (we can easily get that by traversing the grid and collecting the info in first pass) that way we can just subtract and see if we have covered all the fresh oranges or not and then if its not 0 just return the output as -1

Since we only check the neighbours (if any) of each rotten orange its a BFS on a grid

lets try to implement the above logic

import dequue

grid = [[2,1,1],[1,1,0],[0,1,1]]
M = len(grid) # rows 
N = len(grid[0]) # columns
MINUTES_ELAPSED = 0
FRESH_ORANGES = 0


# first pass to collect all the fresh oranges

for i in range(M):
	for j in range(N):
		if grid[i][j] == 1:
			FRESH_ORANGES +=1


# we would now need to do BFS on the grid

now how does the BFS look like

we first need to find where is the rotten orange in the grid since its not mentioned that it will always be at the top left of the grid. so we would need to have a sequential search 2 for loop


for i in range(M):
	for j in range(N):
		if grid[i][j] == 2: # we have found a rotten orage
			BFS(grid[i][j])

but what if we find an orange that was already rotten by a previous rotten orange , so we need to mark it with something that we have already counted it so yes everytime we find a fresh orange we just make it null and void say with “#” so that its not counted again or we can have a hashmap to check if we have already visited it or not just like we have one in [[Clone Graph]] this should be a separate function i believe for BFS

import deque

def BFS(grid_node):
	# since we only have to explore next neighbours it will be
	#  # right left top down  i.e grid[i+1][j] grid[i-1][j] grid[i][j+1] grid[i][j-1]
  • 🍅 (pomodoro::WORK) (duration:: 20m) (begin:: 2025-12-18 10:42) - (end:: 2025-12-18 11:03)

Optimal Solution

You’ve done an incredible job breaking this problem down. Your analysis is sharp, clear, and you’ve correctly identified nearly all the essential components and patterns.

Let’s organize your insights and address the key questions you’ve raised.

Your Insights (All Correct and Excellent):

  1. It’s a Graph Traversal Problem: Correct. A grid is just a specific type of graph where nodes are cells and edges connect to adjacent cells.

  2. BFS is the Right Choice: Your reasoning is perfect.

    “Since we only check the neighbours (if any) of each rotten orange… and then expand progressively”
    This “layer-by-layer” expansion is the very definition of Breadth-First Search (BFS). Using DFS would find a path of rotting, but it wouldn’t correctly model the simultaneous rotting that happens each minute.

  3. Need to Count Fresh Oranges: Correct. You need an initial count of fresh oranges to know at the end if any were impossible to reach.

  4. Handling Multiple Initial Rotten Oranges: You correctly identified that there could be several “2s” at the start.

  5. Avoiding Re-visiting: You correctly realized you need a mechanism (like changing the cell value or using a visited set) to prevent infinite loops or redundant work.

You are on the verge of the complete, optimal algorithm.

Let’s Answer Your “How does the BFS look like?” Question:

This is the core of the problem. A standard BFS uses a queue.

What if we put all of the initially rotten oranges into the queue at the very beginning?

The BFS would then naturally expand outwards from all of them simultaneously, layer by layer. Each “layer” of the BFS corresponds to one minute passing.

Let’s structure the Multi-Source BFS:

  1. Initialization (Your First Pass):
    • Initialize queue = deque().
    • Initialize fresh_oranges = 0.
    • Iterate through the entire grid once to:
      • Find all fresh oranges and increment fresh_oranges.
      • Find all rotten oranges and add their coordinates (r, c) to the queue.
  2. The Main BFS Loop:
    • You need a variable to track time, minutes = 0.
    • The loop should continue as long as there are oranges in the queue and there are still fresh_oranges left to rot.
    • The “Minute” Trick: Inside the while loop, we want to process exactly one “layer” or one “minute’s worth” of rotting at a time. A common way to do this is:
      • Get the current_level_size = len(queue).
      • Run a for loop current_level_size times.
      • Inside this for loop, you pop an orange, rot its neighbors, and push the newly rotten neighbors onto the queue.
      • After this for loop finishes, you have processed exactly one minute’s worth of rotting. You can now increment minutes.

The Self-Nudge Questions:

Question 1: The BFS “Visit” Step

  • When you pop a rotten orange at (r, c) from the queue, what do you do? You need to explore its four neighbors (nr, nc).
  • For each neighbor, what are the conditions that must be true for you to “rot” it? (Hint: It must be in-bounds and it must be a fresh orange).

Question 2: Updating State

  • When you successfully rot a neighbor at (nr, nc):
    • What do you change its value in the grid to?
    • What do you do with its coordinates (nr, nc)?
    • What happens to your fresh_oranges counter?

Question 3: The Final Result

  • After the main while loop finishes, how do you determine the final answer?
  • What does it mean if fresh_oranges is still greater than 0?
  • What is the correct return value in that case? What about the successful case?

(Prompt): Based on this multi-source BFS structure and these questions, try to write the pseudocode for the main part of the algorithm after the initial grid scan. Focus on the while loop, the inner for loop for managing minutes, and the logic for rotting a neighbor.

okay so the idea of counting rotten oranges and adding its coordinates to the queue along with the fresh oranges count is amazing lets do that the second is the bfs loop this going to be interesting

inside the while loop q1 : so for each rotten orange (r,c) we pop it and explore its neighbours (r-1,c) (r+1,c) (r,c-1) (r,c+1) we check if the r and c are within the grid and also if there is a fresh orange or not , if they are fresh and within the grid we then rotten it 1. change its value to “#” invalid 2. decrement the fresh orange counter 3. and add it to the queue for processing After this for loop we increment the minute counter

once the whole while loop is complete we check the fresh orange counter , if its more than 0 we return -1 if its not we return the minutes

below is the python code

import deque

grid = [[2,1,1],[1,1,0],[0,1,1]]


# first pass to collect all the fresh oranges and add rotten oranges to the queue.

def rotten_oranges(grid):

	M = len(grid) # rows 
	N = len(grid[0]) # columns
	MINUTES_ELAPSED = 0
	FRESH_ORANGES = 0
	queue = deque([])
	
	for i in range(M):
		for j in range(N):
			if grid[i][j] == 1: # count the fresh oranges
				FRESH_ORANGES +=1
			elif grid[i][j] == 2: # add the rotten oranges indices to the queue
				queue.append((i,j))

	while queue:
		current_level_size = len(queue)
		for rotten in range(current_level_size):
			current_rotten = queue.popleft()
			neighbours = [[current_rotten[0]+1,current_rotten[1]],
						   [current_rotten[0]-1,current_rotten[1]],
						   [current_rotten[0],current_rotten[1]+1],
						   [current_rotten[0],current_rotten[1]-1],]
			for neighbour in neighbours:
				if neighbour[0] >= M or neighbour[1] >= N or neighbour[0] < 0 or neighbour[1] < 0:
					continue
				if grid[neighbour[0]][neighbour[1]] == 1: # found a fresh 
					grid[neighbour[0]][neighbour[1]] = 2  # make it rotten 
					FRESH_ORANGES -=1
					queue.append((neighbour[0],neighbour[1]))
		MINUTES_ELAPSED +=1

	return MINUTES_ELAPSED if FRESH_ORANGES == 0 else -1

print(rotten_oranges(grid))
  • 🍅 (pomodoro::WORK) (duration:: 30m) (begin:: 2025-12-18 11:04) - (end:: 2025-12-18 12:01)