Skip to main content

22. Rotting Oranges

mediumAsked at Riot Games

Compute the minutes until every fresh orange rots given multi-source spread — Riot tests multi-source BFS to reason about ability radii expanding over server ticks.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an m x n grid where 0 is empty, 1 is fresh, and 2 is rotten, every minute a rotten orange rots its 4-neighbors. Return the minimum minutes until no fresh oranges remain, or -1 if impossible.

Constraints

  • 1 <= m, n <= 10
  • Grid values are 0, 1, or 2

Examples

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

Approaches

1. Iterative single-source sweep

For each rotten orange, run a separate BFS and merge minute values.

Time
O((m*n)^2)
Space
O(m*n)
// Run BFS from each rotten orange independently
// Combine minimum times in a parallel grid
// Wastes work re-walking shared cells

Tradeoff:

2. Multi-source BFS

Seed the queue with every rotten orange and BFS level-by-level, counting fresh oranges and minutes. Mirrors how Riot simulates an AoE ability's spread radius across the minimap in a single tick sweep.

Time
O(m*n)
Space
O(m*n)
function orangesRotting(grid) {
  const m=grid.length, n=grid[0].length;
  const q=[]; let fresh=0;
  for (let r=0;r<m;r++) for (let c=0;c<n;c++) {
    if (grid[r][c]===2) q.push([r,c,0]);
    else if (grid[r][c]===1) fresh++;
  }
  let mins=0;
  const dirs=[[1,0],[-1,0],[0,1],[0,-1]];
  while (q.length) {
    const [r,c,t] = q.shift();
    mins = Math.max(mins, t);
    for (const [dr,dc] of dirs) {
      const nr=r+dr, nc=c+dc;
      if (nr<0||nc<0||nr>=m||nc>=n||grid[nr][nc]!==1) continue;
      grid[nr][nc]=2; fresh--;
      q.push([nr,nc,t+1]);
    }
  }
  return fresh===0 ? mins : -1;
}

Tradeoff:

Riot Games-specific tips

Riot grades whether you seed the BFS queue with all sources at once — the same simultaneous-tick model their game server uses to resolve overlapping ability spreads without per-source recomputation.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Rotting Oranges and other Riot Games interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →