LeetCode 994. Rotting Oranges

Posted on Edited on In , Views:

🧩 Problem Description

You are given an m x n grid where each cell can have one of three values:

  • 0 representing an empty cell,
  • 1 representing a fresh orange,
  • 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange.
If it is impossible, return -1.

💬 Examples

Example 1

1
2
Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

Example 2

1
2
3
Input: grid = [[2,1,1],[0,1,1],[1,0,1]]
Output: -1
Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten.

Example 3

1
2
Input: grid = [[0,2]]
Output: 0

💡 Intuition

This is a multi-source BFS problem.

  • Each rotten orange is a BFS starting point.
  • Use a queue to simulate the spread minute by minute.
  • Track how many fresh oranges remain.
  • If at the end some fresh oranges are left, return -1.

🔢 Java Code (BFS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        Queue<int[]> q = new LinkedList<>();
        int fresh = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    q.offer(new int[]{i, j});
                } else if (grid[i][j] == 1) {
                    fresh++;
                }
            }
        }

        if (fresh == 0) return 0; // no fresh oranges

        int minutes = -1;
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};

        while (!q.isEmpty()) {
            int size = q.size();
            minutes++;
            for (int s = 0; s < size; s++) {
                int[] cur = q.poll();
                for (int[] d : dirs) {
                    int x = cur[0] + d[0], y = cur[1] + d[1];
                    if (x < 0 || y < 0 || x >= m || y >= n || grid[x][y] != 1) continue;
                    grid[x][y] = 2;
                    fresh--;
                    q.offer(new int[]{x, y});
                }
            }
        }

        return fresh == 0 ? minutes : -1;
    }
}

⏱ Time and Space Complexity

  • Time Complexity: O(m × n), each cell is visited at most once.
  • Space Complexity: O(m × n) for the BFS queue.

✍️ Summary

  • Treat all rotten oranges as starting points.
  • Run BFS layer by layer to simulate time passing.
  • Return minutes when all fresh oranges are rotten, otherwise -1.

Related problems

  • lc-286 — Walls and Gates
  • lc-542 — 01 Matrix
  • lc-200 — Number of Islands