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, or2 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.
Constraints:
m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j] is 0, 1, or 2.The key idea behind #994 Rotting Oranges is to simulate how rot spreads across the grid over time. Each rotten orange can infect its adjacent fresh oranges (up, down, left, right) every minute. This spreading behavior naturally fits a multi-source Breadth-First Search (BFS) approach.
Start by scanning the matrix to place all initially rotten oranges into a queue. These act as the starting points of infection. During each BFS level (representing one minute), process the current rotten oranges and convert any adjacent fresh oranges into rotten ones, adding them to the queue for the next round.
Track the number of fresh oranges remaining and the time elapsed as BFS progresses. If BFS finishes and fresh oranges still exist, it means some were unreachable. The algorithm visits each cell at most once, leading to a time complexity of O(m × n) and space complexity of O(m × n) for the queue and grid traversal.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Multi-source BFS (grid traversal) | O(m × n) | O(m × n) |
take U forward
This approach uses BFS to simulate the rotting process of the oranges. We start with all initially rotten oranges and spread the rot to the 4-adjacent fresh oranges, time step by time step. We use a queue to implement BFS, where each element in the queue represents a rotten orange at a specific time. The key idea is that in one minute, all current rotten oranges will rot their 4-directionally adjacent fresh oranges.
Time Complexity: O(m * n), where m and n are the number of rows and columns in the grid. Each cell is processed at most once.
Space Complexity: O(m * n) for the queue, in the worst case.
1from collections import deque
2
3def orangesRotting(grid):
4 rows, cols = len(grid), len(grid[0])
5 queue = deque()
6 fresh_count = 0
7 time_elapsed = 0
8
9 for r in range(rows):
10 for c in range(cols):
11 if grid[r][c] == 2:
12 queue.append((r, c, 0))
13 elif grid[r][c] == 1:
14 fresh_count += 1
15
16 while queue and fresh_count > 0:
17 r, c, minutes = queue.popleft()
18 for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
19 nr, nc = r + dr, c + dc
20 if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
21 grid[nr][nc] = 2
22 fresh_count -= 1
23 queue.append((nr, nc, minutes + 1))
24 time_elapsed = minutes + 1
25
26 return time_elapsed if fresh_count == 0 else -1We initialize a queue with the position of all rotten oranges (value 2) and their corresponding time, which is 0 initially. We also keep a count of fresh oranges. For each iteration, we process rotten oranges, spread the rot, and keep track of the time taken for each step. If at the end there are still fresh oranges left, we return -1.
Instead of using BFS, this approach converts the problem to a depth-first search with memoization. By examining from each fresh orange, one can determine its minimum time to rot by considering all possible paths of infection.
Time Complexity: O(m * n), as each cell is processed recursively.
Space Complexity: O(m * n) because of the memoization table and the call stack in recursion.
1public int orangesRotting(int[][] grid) {
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Rotting Oranges is a common interview problem because it tests grid traversal, BFS concepts, and simulation logic. Variations of multi-source BFS problems frequently appear in technical interviews at top tech companies.
A queue is the most suitable data structure because the problem models a level-by-level spreading process. Using a queue allows BFS traversal so that all oranges infected at the same time are processed together.
The optimal approach uses multi-source Breadth-First Search (BFS). All initially rotten oranges are inserted into a queue and spread the rot level by level to adjacent fresh oranges. Each BFS level represents one minute of time.
BFS is preferred because it processes nodes level by level, which naturally represents the passage of time in minutes. DFS does not guarantee this layer-by-layer progression, making it harder to accurately track the minimum time required.
This solution uses depth-first search (DFS) and memoization to find the shortest path from a fresh orange to a rotten one. Each fresh orange recursively checks all possible paths to rotten oranges, updating the minimum time via memoization.