Rotting Oranges
Rotting Oranges 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.
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
- All coding practice problems
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
- Word Ladder — Hard, same subpattern
- Accounts Merge — Medium, same pattern
- Alien Dictionary — Hard, same pattern
- All Paths from Source Lead to Destination — Medium, same pattern