Skip to main content

18. Rotting Oranges

mediumAsked at JetBrains

Compute the minutes until all oranges rot via 4-directional spread — JetBrains uses this to test level-based BFS, the primitive behind their incremental-rebuild scheduling.

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

Problem

Given an m x n grid where 0=empty, 1=fresh, 2=rotten, return the minimum minutes for every fresh orange to rot. Rotten oranges infect 4-directional neighbors each minute. Return -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. Iterate until stable

Each minute, scan the grid and convert any fresh orange next to a rotten one; quadratic.

Time
O((m*n)^2)
Space
O(m*n)
// repeat full-grid scan every minute until no fresh updates

Tradeoff:

2. Multi-source BFS by level

Seed the queue with every rotten orange, BFS level by level counting minutes, tracking the fresh count. If fresh > 0 at the end, return -1. Same level-BFS shape JetBrains schedulers use for staged compile waves.

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 i=0;i<m;i++) for (let j=0;j<n;j++) {
    if (grid[i][j]===2) q.push([i,j]);
    else if (grid[i][j]===1) fresh++;
  }
  let minutes = 0;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  while (q.length && fresh) {
    const next = [];
    for (const [i,j] of q) {
      for (const [dx,dy] of dirs) {
        const ni=i+dx, nj=j+dy;
        if (ni<0||nj<0||ni>=m||nj>=n||grid[ni][nj]!==1) continue;
        grid[ni][nj] = 2; fresh--; next.push([ni,nj]);
      }
    }
    q.length = 0; q.push(...next);
    minutes++;
  }
  return fresh === 0 ? minutes : -1;
}

Tradeoff:

JetBrains-specific tips

JetBrains expects you to draw the analogy to staged rebuilds — the same minute-by-minute level-BFS expansion mirrors how their build systems propagate dirty markers wave by wave.

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

Practice these live with InterviewChamp.AI →