Command Palette

Search for a command to run...

Hectal
Problem 21.1 · Breadth-First SearchMedium

Rotting Oranges

PatternGraph BFSMatrix Traversal

What it teaches: Multi-source BFS on a grid, counting levels as minutes.

Practise it on judges as “Rotting Oranges”.

The problem

Cells are 0 (empty), 1 (fresh orange) or 2 (rotten). Each minute, fresh oranges next to a rotten one (up, down, left, right) rot. Return the minutes until no fresh orange remains, or −1 if that never happens.

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

Constraints

  • 1 ≤ rows, cols ≤ 10

Pattern clues in the wording

  • → Spreading from many sources at once
  • → Time = number of steps

These clues point to Graph BFS: Explore from a start node in rings of increasing distance using a queue and a visited set.

Stuck? Take one hint at a time

Solution.java · starter
import java.util.*;

class Solution {
    public int orangesRotting(int[][] grid) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#InputExpected
1
grid = [[2,1,1],[1,1,0],[0,1,1]]
4
2
grid = [[2,1,1],[0,1,1],[1,0,1]]
-1
3
grid = [[0,2]]
0

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Multi-source BFS · O(rows × cols)
1

Multi-source BFS

Time O(rows × cols) Space O(rows × cols)

Queue all 2s, count 1s. Process level by level; each level that rots something is one minute. At the end, if fresh > 0 return −1.

Approach 1
import java.util.*;

class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length, fresh = 0;
        Deque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < m; r++)
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 2) q.offer(new int[]{r, c});
                else if (grid[r][c] == 1) fresh++;
            }
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int minutes = 0;
        while (!q.isEmpty() && fresh > 0) {
            minutes++;
            for (int size = q.size(); size > 0; size--) {
                int[] cell = q.poll();
                for (int[] d : dirs) {
                    int r = cell[0] + d[0], c = cell[1] + d[1];
                    if (r < 0 || c < 0 || r >= m || c >= n || grid[r][c] != 1) continue;
                    grid[r][c] = 2;
                    fresh--;
                    q.offer(new int[]{r, c});
                }
            }
        }
        return fresh == 0 ? minutes : -1;
    }
}

Verdict: One BFS for all sources.

Before you submit

Edge cases and common mistakes

Test these inputs

  • No fresh oranges (0)
  • Fresh orange with no rotten neighbour path (−1)
  • No rotten oranges but fresh ones exist (−1)

Mistakes people make

  • Counting one extra minute for the last, empty level.
  • Running BFS from each rotten orange separately.

Interview

Follow-up questions

How would you return the minute each orange rots?