994. Rotting Oranges

How to solve Rotting Oranges (LeetCode 994): the approach in brief

The problem

You are given an m x n grid where each cell can have one of three values:

Pattern

Rotting Oranges is a Graph Traversal Patterns (DFS & BFS) problem, in the Graph BFS - Connected Components / Island Counting subpattern. The pattern covers DFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST

Use BFS for shortest path in unweighted graphs. Solve word ladder, rotting oranges, and matrix problems.

Approach outline

1. Consider modeling the grid as a graph where each cell is a node connected to its adjacent cells to track the spread of rot.
2. Think about using a Breadth-First Search (BFS) starting from all rotten oranges simultaneously to simulate the minute-by-minute infection spread.
3. Use a queue to process all rotten oranges at the current minute before moving to the next, which helps in tracking the time elapsed.

Complexity

The reference solution runs in O(m * n) time and O(m * n) space.

Asked at

Rotting Oranges has been reported in interviews at Amazon, Bloomberg, Flipkart, Google, Microsoft, Oracle, Walmart Labs.