994. Rotting Oranges
Rotting Oranges (LeetCode 994) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph BFS - Connected Components / Island Counting subpattern.
How to solve Rotting Oranges
Rotting Oranges is a BFS Connected Components problem, part of Graph Traversal Patterns (DFS & BFS). Use BFS for shortest path in unweighted graphs. Solve word ladder, rotting oranges, and matrix problems.
Work towards the solution in these steps:
- Consider modeling the grid as a graph where each cell is a node connected to its adjacent cells to track the spread of rot.
- Think about using a Breadth-First Search (BFS) starting from all rotten oranges simultaneously to simulate the minute-by-minute infection spread.
- Use a queue to process all rotten oranges at the current minute before moving to the next, which helps in tracking the time elapsed.
The reference solution runs in O(m * n) time and O(m * n) space.
The Rotting Oranges solution and editorial walks through the full approach with reference code.
Problem statement
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.
Constraints:
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 10
- grid[i][j] is 0, 1, or 2.
Topics and companies
Topics: Array, Breadth-First Search, Matrix.
Reported in interviews at Amazon, Bloomberg, Flipkart, Google, Microsoft, Oracle, Walmart Labs.
How to practise Rotting Oranges on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n) time and O(m * n) space.
Open Rotting Oranges in the code editor, or read the Rotting Oranges editorial for a worked solution with its approach and complexity analysis.
Where Rotting Oranges sits in the DSA pattern sheet
- Graph Traversal Patterns (DFS & BFS) pattern guide
- Graph BFS - Connected Components / Island Counting subpattern
- The full DSA patterns sheet
Problems related to Rotting Oranges
Other problems that use the same Graph BFS - Connected Components / Island Counting and Graph Traversal Patterns (DFS & BFS) techniques:
- 01 Matrix — Medium, same subpattern
- Shortest Path in Binary Matrix — Medium, same subpattern
- Walls and Gates — Medium, same subpattern
- Word Ladder — Hard, same subpattern
- Accounts Merge — Medium, same pattern
- Alien Dictionary — Hard, same pattern
Rotting Oranges FAQ
What is the LeetCode number of Rotting Oranges?
Rotting Oranges is LeetCode problem 994, rated Medium.
What pattern is used to solve Rotting Oranges?
Rotting Oranges is a BFS Connected Components problem. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph BFS - Connected Components / Island Counting subpattern.
What is the time complexity of Rotting Oranges?
The reference solution runs in O(m * n) time and O(m * n) space.
Which companies ask Rotting Oranges?
Rotting Oranges has been reported in interviews at Amazon, Bloomberg, Flipkart, Google, Microsoft, Oracle, Walmart Labs.