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.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.
We 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.
JavaScript
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.
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.
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.
C#
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.
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) | 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. |
| DFS with memoization | Time Complexity: O(m * n), as each cell is processed recursively. |
G-10. Rotten Oranges | C++ | Java • take U forward • 413,032 views views
Watch 9 more video solutions →Practice Rotting Oranges with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor