Coding Interview PatternsRotting Oranges
MediumGraphs

Rotting Oranges

Explanation & Solution

Practice Problem

Description

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
  • 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.

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]

Output: 4

Explanation: At minute 0 the top-left orange is rotten. It takes 4 minutes for all fresh oranges to become rotten.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] is 0, 1, or 2

Approach

Graphs pattern

1. Scan the Grid

  • Iterate through every cell in the grid
  • Push every rotten orange (r, c) into a queue — these are the BFS starting points
  • Count the total number of fresh oranges

2. Handle the Trivial Case

  • If freshCount === 0 there is nothing to rot, so return 0 immediately

3. Multi-Source BFS — Process Level by Level

  • Each level of the BFS represents one minute of elapsed time
  • For each cell in the current level, check all 4 neighbors (up, down, left, right)
  • If a neighbor is a fresh orange, mark it rotten (grid[nr][nc] = 2), decrement freshCount, and push it into the queue for the next level

4. Increment the Timer

  • After processing all cells in the current level, if there are new cells in the queue (meaning fresh oranges were rotted this round), increment minutes

5. Check for Unreachable Oranges

  • After BFS completes, if freshCount > 0 some oranges were never reached — return -1
  • Otherwise return minutes

Key Insight

  • Multi-source BFS starts from all rotten oranges simultaneously, expanding outward one layer per minute — this naturally gives the shortest time for every reachable fresh orange to rot
Time
O(m × n)every cell is visited at most once
Space
O(m × n)in the worst case the queue holds every cell

Visualization

Input:
Multi-Source BFS3×3 grid
012012211110011
output—

Press play to start multi-source bfs

CurrentQueuedVisitedSource
20 steps

Solution Code

Previous
Number of Provinces
Next
Walls and Gates