Rotting Oranges

NeetCode: Rotting Oranges · LeetCode: 994. Rotting Oranges · Difficulty: Medium

In a grid, 0 is an empty cell, 1 a fresh orange, and 2 a rotten orange. Every minute, each fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes until no fresh orange remains, or -1 if that is impossible.

Example

Text

grid: 2 1 1     Output: 4
      1 1 0
      0 1 1

grid: 2 1 1     Output: -1   (the bottom-left orange is never adjacent to rot)
      0 1 1
      1 0 1

grid: 0 2       Output: 0

Brute force: simulate minute by minute

Follow the statement literally. Each minute, scan the whole grid, build the next state where every fresh orange next to a rotten one is now rotten, and stop when nothing changes. Any fresh orange left at the end means -1. Every minute rescans all cells even though only the rotting frontier changes. Java arrays are objects, so the copy of the grid is made row by row with clone().

Java

class Solution {
    public int orangesRotting(int[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int minutes = 0;
        while (true) {
            int[][] next = new int[m][];
            for (int r = 0; r < m; r++) {
                next[r] = grid[r].clone();
            }
            boolean changed = false;
            for (int r = 0; r < m; r++) {
                for (int c = 0; c < n; c++) {
                    if (grid[r][c] != 1) {
                        continue;
                    }
                    boolean rottenNb = (r > 0 && grid[r - 1][c] == 2)
                        || (r + 1 < m && grid[r + 1][c] == 2)
                        || (c > 0 && grid[r][c - 1] == 2)
                        || (c + 1 < n && grid[r][c + 1] == 2);
                    if (rottenNb) {
                        next[r][c] = 2;
                        changed = true;
                    }
                }
            }
            if (!changed) {
                break;
            }
            grid = next;
            minutes++;
        }
        for (int[] row : grid) {
            for (int cell : row) {
                if (cell == 1) {
                    return -1;
                }
            }
        }
        return minutes;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.orangesRotting(new int[][]{{2, 1, 1}, {1, 1, 0}, {0, 1, 1}}));
        System.out.println(s.orangesRotting(new int[][]{{2, 1, 1}, {0, 1, 1}, {1, 0, 1}}));
        System.out.println(s.orangesRotting(new int[][]{{0, 2}}));
        System.out.println(s.orangesRotting(new int[][]{{0}}));
    }
}

Output

Time: O((m * n)^2) worst case: a long snake of oranges rots in about m * n / 2 minutes and each minute costs O(m * n). Space: O(m * n) for the copy of the grid.

Optimal: multi-source BFS

Rotting spreads outward one step per minute, which is exactly what BFS does: one BFS level equals one minute. Put all initially rotten oranges into the queue at once (they all start at time 0), count the fresh oranges, and expand level by level. Each orange is enqueued once, when it rots. Afterwards, if the fresh counter is not zero, some orange was unreachable and the answer is -1. The queue is an ArrayDeque<int[]> of {row, column} pairs. queue.size() is read before the inner loop so that only the current level is processed.

Java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int orangesRotting(int[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        Deque<int[]> queue = new ArrayDeque<>();
        int fresh = 0;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 2) {
                    queue.add(new int[]{r, c});
                } else if (grid[r][c] == 1) {
                    fresh++;
                }
            }
        }
        int minutes = 0;
        while (fresh > 0 && !queue.isEmpty()) {
            minutes++;
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                int[] cell = queue.poll();
                for (int[] d : DIRS) {
                    int nr = cell[0] + d[0];
                    int nc = cell[1] + d[1];
                    if (nr < 0 || nc < 0 || nr >= m || nc >= n) {
                        continue;
                    }
                    if (grid[nr][nc] == 1) {
                        grid[nr][nc] = 2;
                        fresh--;
                        queue.add(new int[]{nr, nc});
                    }
                }
            }
        }
        return fresh == 0 ? minutes : -1;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.orangesRotting(new int[][]{{2, 1, 1}, {1, 1, 0}, {0, 1, 1}}));
        System.out.println(s.orangesRotting(new int[][]{{2, 1, 1}, {0, 1, 1}, {1, 0, 1}}));
        System.out.println(s.orangesRotting(new int[][]{{0, 2}}));
        System.out.println(s.orangesRotting(new int[][]{{0}}));
    }
}

Output

The loop stops as soon as fresh reaches zero, so no minute is counted for a final level that rots nothing. This also gives 0 for grids that start with no fresh orange. Time: O(m * n). Space: O(m * n) for the queue.