mediumGraphs & BFS/DFS

Rotting Oranges

Each minute, rotten oranges rot their horizontally or vertically adjacent fresh neighbors. Find when all fresh oranges have rotted.

LeetCode ↗

Work through the cases

3 examples

Input notation

Space-separated grid rows: 0 is empty, 1 is fresh, 2 is rotten.

Expected result

Minutes required, or -1 if some fresh oranges cannot rot.

Case 1

Input

2 1 1
0 1 1

Expected output

Case 2

Input

2 0 1

Expected output

-1

Case 3

Input

0 2

Expected output

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Rot spreads to four-neighbors each minute; we want the time until every orange is rotten. Simultaneous multi-source spread is an unweighted shortest path. Enqueue every rotten orange and count the fresh ones, then BFS by layers. The layer that zeroes the fresh count is the answer; leftover fresh oranges yield -1.

First, we traverse the entire grid once, count the number of fresh oranges, denoted as cnt, and add the coordinates of all rotten oranges to the queue q.

Next, we perform a breadth-first search. In each round of the search, we let all the rotten oranges in the queue rot the fresh oranges in four directions, until the queue is empty or the number of fresh oranges is 0.

Finally, if the number of fresh oranges is 0, we return the current round number, otherwise, we return -1.

The time complexity is O(m × n), and the space complexity is O(m × n). Where m and n are the number of rows and columns of the grid, respectively.

class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        Deque<int[]> q = new ArrayDeque<>();
        int cnt = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    ++cnt;
                } else if (grid[i][j] == 2) {
                    q.offer(new int[] {i, j});
                }
            }
        }
        final int[] dirs = {-1, 0, 1, 0, -1};
        for (int ans = 1; !q.isEmpty() && cnt > 0; ++ans) {
            for (int k = q.size(); k > 0; --k) {
                var p = q.poll();
                for (int d = 0; d < 4; ++d) {
                    int x = p[0] + dirs[d], y = p[1] + dirs[d + 1];
                    if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
                        grid[x][y] = 2;
                        q.offer(new int[] {x, y});
                        if (--cnt == 0) {
                            return ans;
                        }
                    }
                }
            }
        }
        return cnt > 0 ? -1 : 0;
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.

Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.