LeetCode 994 Rotting Oranges - Example and Complexity Analysis

Trace the example grid.

Initial: queue = [(0,0)], fresh = 6.

Minute 1: (0,0) rots neighbors. (0,1) and (1,0) rot. Queue = [(0,1), (1,0)]. Fresh = 4.

Minute 2: (0,1) rots (0,2). (1,0) rots (1,1). Fresh = 2.

Minute 3: (0,2) has no fresh neighbors. (1,1) rots (2,1). Fresh = 1.

Minute 4: (2,1) rots (2,2). Fresh = 0.

Queue empty. Fresh = 0. Return 4.

Each cell processed at most once. $O(m \cdot n)$ time. $O(m \cdot n)$ space for queue.