Skip to main content

20. Rotting Oranges

mediumAsked at Flipkart

Compute the minutes until all fresh oranges rot in a 4-connected grid — Flipkart uses it to test multi-source BFS, the same model behind warehouse stockout propagation.

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, each minute a rotten orange rots all 4-directional fresh neighbors. Return the minimum minutes until none are fresh, or -1 if impossible.

Constraints

  • 1 <= m, n <= 10
  • grid[i][j] in {0,1,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. Single-source repeated DFS

Run BFS from each rotten cell separately and take the max — wasteful.

Time
O((m*n)^2)
Space
O(m*n)
// recompute distances from every rotten cell — repeated work

Tradeoff:

2. Multi-source BFS

Seed a queue with every rotten cell at minute 0 and BFS once. Track remaining fresh count; the level when the queue empties is the answer.

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

Tradeoff:

Flipkart-specific tips

Flipkart panels reward the multi-source framing — they apply it for cascading inventory-snapshot updates across warehouse clusters.

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

Practice these live with InterviewChamp.AI →