Start learning free

LESSON 472 OF 536 · GRAPHS

Rotting Oranges in Java: Multi-Source BFS on a Grid

Practice O(m · n) Read the full explanation

You are given a grid grid with m rows and n columns: an array of rows, where each row is an array of integers. Rows are numbered from 0, top to bottom, and columns from 0, left to right. Every cell holds one of three values:

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

Every minute, each fresh orange that is next to a rotten orange (up, down, left or right, not diagonally) becomes rotten.

Return the number of minutes that pass until no cell holds a fresh orange. If some orange can never rot, return -1.

 

Example 1:

Input: grid = [
  [2, 1, 1],
  [1, 1, 0],
  [0, 1, 1]
]
Output: 4
Explanation: The grid after each minute:
  start      minute 1   minute 2   minute 3   minute 4
  2 1 1      2 2 1      2 2 2      2 2 2      2 2 2
  1 1 0      2 1 0      2 2 0      2 2 0      2 2 0
  0 1 1      0 1 1      0 1 1      0 2 1      0 2 2
In minute 1 the two oranges next to the rotten one in the corner rot; in each later minute the
oranges next to those rot in turn. After minute 4 no orange is fresh.

Example 2:

Input: grid = [
  [2, 1, 1],
  [0, 1, 1],
  [1, 0, 1]
]
Output: -1
Explanation: The orange in the bottom left corner, [2, 0], has an empty cell above it and to
its right. Rot doesn't spread diagonally, so nothing ever reaches it: it stays fresh forever.

Example 3:

Input: grid = [[0, 2]]
Output: 0
Explanation: No orange is fresh at the start, so no minute has to pass.

 

Constraints:

  • 1 <= m, n <= 300
  • Every row has n values.
  • Every grid[r][c] is 0, 1 or 2.

Note:

Your algorithm should run in O(m · n) time and use O(m · n) extra space.

Simulating the grid minute by minute, with a scan of every cell in each minute, can cost O((m · n)2): think of a long winding line of oranges that the rot creeps along one cell per minute. The tutorial uses a BFS that starts from all the rotten oranges at once, as the BFS in 01 Matrix starts from all the zeros, and goes through it level by level: the oranges that rot in minute 1 are the first level, the oranges they rot are the second level, and so on, so the number of levels is the number of minutes. A count of the fresh oranges, lowered each time one rots, tells at the end whether some orange never rotted. Each cell joins the queue at most once.

STEP 1 OF 23
    Ctrl + Enter to check

    JAVA · GRAPHS

    Rotting Oranges in Java, explained

    Problem overview

    The method orangesRotting(int[][] grid) receives a grid where 0 is an empty cell, 1 is a fresh orange and 2 is a rotten orange. Every minute, each fresh orange that is next to a rotten one (up, down, left or right, not diagonally) becomes rotten. The method returns the number of minutes until no cell holds a fresh orange, or -1 if some orange can never rot.

    In the first example the grid is [[2,1,1],[1,1,0],[0,1,1]]. The rot starts in the top-left corner and creeps one cell per minute, and the last orange, in the bottom-right corner, rots in minute 4, so the answer is 4. In the second example, [[2,1,1],[0,1,1],[1,0,1]], the orange in the bottom-left corner has an empty cell above it and to its right. Rot doesn't spread diagonally, so it stays fresh forever and the answer is -1. In the third, [[0,2]], nothing is fresh at the start, so the answer is 0.

    Approach: spread level by level from all rotten oranges

    Simulating the grid minute by minute, scanning every cell each time, can cost O((m · n)²): picture a long winding line of oranges that the rot creeps along one cell per minute. A better way is a breadth-first search (BFS) that starts from every rotten orange at once.

    The BFS keeps a queue of rotten oranges that are about to spread the rot. Everything that rots in minute 1 is the first level, everything those oranges rot is the second level, and so on. The number of levels processed is the number of minutes. Each orange joins the queue at most once, when it rots, so the whole search is O(m · n).

    A counter fresh tells when to stop. It starts as the number of fresh oranges and goes down each time one rots. When it reaches 0, the work is done. If the queue runs empty while fresh is still above 0, no chain of oranges connects the rest to a rotten one, and the answer is -1.

    The grid itself serves as the visited marker: turning a cell into 2 as soon as it rots means no other orange rots it again or queues it a second time. After the call on the first example, the grid reads:

    2 2 2
2 2 0
0 2 2

    For the second example, the call leaves the grid like this, with the bottom-left orange still fresh:

    2 2 2
0 2 2
1 0 2

    Step by step

    1. Store the grid's size. rows is grid.length and cols is grid[0].length. Every row has the same length, so the first row's length is the number of columns.
    2. Create the queue as an ArrayDeque declared as Deque<int[]>. Each entry is a {row, column} pair. add puts a cell at the back and poll takes one from the front, both in O(1).
    3. Create fresh, starting at 0.
    4. Scan the whole grid with two loops over r and c.
    5. Queue every rotten orange. When grid[r][c] == 2, add new int[]{r, c}. All oranges rotten at the start spread the rot in the first minute, so all of them go in before the search begins.
    6. Count every fresh orange. When grid[r][c] == 1, do fresh++. Empty cells are neither.
    7. Define directions. The four moves are {-1, 0} up, {1, 0} down, {0, -1} left and {0, 1} right. Each changes the row or the column by one, never both, so diagonal oranges aren't neighbours.
    8. Create minutes, starting at 0. If nothing is fresh at the start, no time passes.
    9. Loop while !queue.isEmpty() && fresh > 0. Each turn is one minute. Without fresh > 0 the loop would count one extra minute after the last orange rots, while the last rotten oranges look for fresh neighbours that are gone.
    10. Count the minute with minutes++.
    11. Freeze the level. Store queue.size() in levelSize. The oranges that rot during this minute join the same queue, but they spread rot only in the next minute, so this minute handles exactly levelSize oranges.
    12. Loop levelSize times, taking the front cell with poll() and reading its row and col from cell[0] and cell[1].
    13. Try the four neighbours. For each d in directions, compute nextRow and nextCol.
    14. Check the bounds first, then the cell. If it is inside the grid and holds a fresh orange (grid[nextRow][nextCol] == 1), rot it by setting it to 2, subtract 1 from fresh, and add it to the queue.
    15. After the loop, return -1 if fresh > 0, otherwise return minutes.

    The solution in Java

    class Solution {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        Deque<int[]> queue = new ArrayDeque<>();
        int fresh = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) {
                    queue.add(new int[]{r, c});
                }
                if (grid[r][c] == 1) {
                    fresh++;
                }
            }
        }
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int minutes = 0;
        while (!queue.isEmpty() && fresh > 0) {
            minutes++;
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                int[] cell = queue.poll();
                int row = cell[0];
                int col = cell[1];
                for (int[] d : directions) {
                    int nextRow = row + d[0];
                    int nextCol = col + d[1];
                    if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols && grid[nextRow][nextCol] == 1) {
                        grid[nextRow][nextCol] = 2;
                        fresh--;
                        queue.add(new int[]{nextRow, nextCol});
                    }
                }
            }
        }
        if (fresh > 0) {
            return -1;
        }
        return minutes;
    }
}

    The Java details worth a closer look:

    • Short-circuit &&. In the neighbour test, the bounds checks come before grid[nextRow][nextCol]. Java stops at the first false, so the grid is read only for cells that exist. Reversing the order would throw an ArrayIndexOutOfBoundsException for neighbours off the edge.
    • Queues of arrays. Deque<int[]> holds one small array per cell, {row, col}. You can't write Deque<int>, because generic type arguments must be object types, but int[] is an object type.
    • ArrayDeque as a queue. add appends at the back and poll removes from the front, giving first-in, first-out order. poll returns null for an empty queue, but the code only polls levelSize times after reading the size.
    • Array initialiser. int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; is the short form for declaring and filling an array in one statement.
    • The input grid is changed. Arrays are passed by reference, so the method rots the caller's grid. Copy it first if you need the original.

    Complexity

    Let the grid have m rows and n columns.

    Time: O(m · n). The first scan touches every cell once. In the search, each cell is added to the queue at most once, and each queued cell looks at four neighbours.

    Space: O(m · n). In the worst case most of the grid sits in the queue at once, for example when many cells are rotten at the start.

    Edge cases and common mistakes

    • No fresh oranges. [[0, 2]], [[2]] and [[0]] all return 0, because the loop never starts.
    • Fresh oranges and no rotten one. [[1]] returns -1: the queue is empty and fresh is 1.
    • Unreachable oranges. A fresh orange walled off by empty cells, or sitting only diagonally next to rot, is never reached, so the answer is -1.
    • Several rotten oranges at the start. [[2,1,1],[1,1,1],[0,0,2]] returns 2: both rotten oranges spread at the same time, which is why all of them are queued before the search.
    • A line. [[2,1,1,1,1]] returns 4: one cell per minute.
    • Counting an extra minute. Without fresh > 0 in the loop condition, the last level would run once more and the answer would be one too large.
    • Not marking cells. If a rotted orange isn't set to 2 immediately, two neighbours can queue it twice and fresh goes wrong.
    • Reading levelSize inside the loop. The queue grows as oranges rot, so queue.size() must be stored before the loop, or the levels would blur together.

    Testing

    • [[2,1,1],[1,1,0],[0,1,1]] gives 4.
    • [[2,1,1],[0,1,1],[1,0,1]] gives -1.
    • [[0,2]] gives 0.
    • [[1]] gives -1.
    • [[2,1,1],[1,1,1],[0,0,2]] gives 2.
    • [[2,1,1,1,1]] gives 4.
    Keep going with Java500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free