Skip to main content

17. Rotting Oranges

mediumAsked at Rappi

Compute the minimum minutes until every fresh orange is rotten given grid spread rules — Rappi frames this as the minimum dispatch ticks until a supply-shortage hotspot propagates across an entire delivery zone.

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

Problem

In an m x n grid, 0 = empty, 1 = fresh orange, 2 = rotten orange. Every minute, any fresh orange adjacent to a rotten one becomes rotten. Return the minimum minutes until no fresh orange remains, or -1 if impossible.

Constraints

  • 1 <= m, n <= 10
  • grid[i][j] is 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. Repeated full-grid sweep

Each minute, scan the grid and turn fresh oranges adjacent to rotten ones; repeat until stable.

Time
O((mn)^2)
Space
O(mn)
// repeat: scan grid, flip newly adjacent fresh to rotten; stop when no change. quadratic across cells.

Tradeoff:

2. Multi-source BFS

Seed the queue with every rotten orange, then BFS in layers — each layer is one minute; the layer count when fresh hits 0 is the answer.

Time
O(mn)
Space
O(mn)
function orangesRotting(g) {
  const q = []; let fresh = 0;
  for (let i=0;i<g.length;i++) for (let j=0;j<g[0].length;j++) {
    if (g[i][j]===2) q.push([i,j,0]);
    if (g[i][j]===1) fresh++;
  }
  let t = 0;
  while (q.length) {
    const [i,j,d] = q.shift();
    t = d;
    for (const [di,dj] of [[1,0],[-1,0],[0,1],[0,-1]]) {
      const ni = i+di, nj = j+dj;
      if (g[ni]?.[nj] === 1) { g[ni][nj] = 2; fresh--; q.push([ni,nj,d+1]); }
    }
  }
  return fresh ? -1 : t;
}

Tradeoff:

Rappi-specific tips

Rappi specifically grades whether you seed all rotten cells at level 0 — single-source BFS is the canonical wrong answer and they'll counter with a multi-rotten-source test case.

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 Rappi interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →