Sponsored
Sponsored
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) {
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.