Minimum time required to rot all oranges

The problem, simply

You get a grid, like a crate of oranges with m rows and n columns. Each spot holds 0 (empty), 1 (a fresh orange) or 2 (a rotten orange).

Every minute, each rotten orange makes the fresh oranges right next to it rotten: up, down, left and right, not on a slant. Give back the number of minutes until no fresh orange is left. If some fresh orange can never be reached, give back -1.

A story to remember it

Picture it

Examples

Way 1: the simple way

Play it out minute by minute.

1. Look at every spot. Mark each fresh orange that touches a rotten one.
2. If nobody was marked, stop. Otherwise turn all marked oranges rotten and add one minute.
3. When you stop, if any fresh orange is left, return -1. Otherwise return the minutes.

Marking first and rotting after is important: an orange that rots this minute must not spread rot in the same minute.

import java.util.*;

class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length, minutes = 0;
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        while (true) {
            List<int[]> toRot = new ArrayList<>();
            for (int r = 0; r < m; r++) {
                for (int c = 0; c < n; c++) {
                    if (grid[r][c] != 1) continue;
                    for (int[] d : dirs) {
                        int nr = r + d[0], nc = c + d[1];
                        if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 2) {
                            toRot.add(new int[]{r, c});    // mark now, rot later
                            break;
                        }
                    }
                }
            }
            if (toRot.isEmpty()) break;
            for (int[] p : toRot) grid[p[0]][p[1]] = 2;
            minutes++;
        }
        for (int[] row : grid) for (int v : row) if (v == 1) return -1;
        return minutes;
    }
}

How long it takes: each minute scans all m * n spots, and there can be up to about m * n minutes (think of a long snake of oranges), so O((m*n)^2). Extra room: the marked list, O(m*n).

Way 2: the clever way

Only oranges that just rotted can spread rot next. So keep them in a waiting line, a queue, and never scan the whole crate again.

1. Scan once. Put every rotten orange in the queue, all together. Count the fresh oranges.
2. While the queue is not empty and fresh oranges remain: read the queue's size. That many oranges form this minute's ring.
3. Take each of them from the front. Every fresh neighbor turns rotten, the fresh count goes down by one, and the neighbor joins the back of the queue.
4. After the ring, add one minute.
5. At the end, return the minutes if the fresh count is 0, else -1.

import java.util.*;

class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length, n = grid[0].length, fresh = 0;
        Queue<int[]> queue = new ArrayDeque<>();
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 2) queue.offer(new int[]{r, c});   // all sources start together
                else if (grid[r][c] == 1) fresh++;
            }
        }
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int minutes = 0;
        while (!queue.isEmpty() && fresh > 0) {
            int ring = queue.size();                 // oranges that rotted last minute
            for (int i = 0; i < ring; i++) {
                int[] cell = queue.poll();
                for (int[] d : dirs) {
                    int nr = cell[0] + d[0], nc = cell[1] + d[1];
                    if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] == 1) {
                        grid[nr][nc] = 2;            // rot it right away so nobody counts it twice
                        fresh--;
                        queue.offer(new int[]{nr, nc});
                    }
                }
            }
            minutes++;
        }
        return fresh == 0 ? minutes : -1;
    }
}

How long it takes: every spot joins the queue at most once and looks at 4 neighbors, O(m*n). Extra room: the queue can hold many spots at once, O(m*n).

Watch out for

• Running a separate search from each rotten orange. It only works if you keep, for every orange, the smallest time over all sources, and it costs O((m*n)^2) when there are many sources. Put all sources in one queue instead.
• Rotting a neighbor but not marking it right away. Another orange in the same ring may add it to the queue a second time.
• No fresh oranges at the start: the answer is 0, even if there are no rotten ones either.
• Changing the input grid. If the caller needs it later, copy it first.

What interviewers ask next

• Return the minute each orange rotted, not only the last one. Store the ring number in a separate grid as you rot each orange.
• Distance from every spot to the nearest 1 in a 0 and 1 grid. Same idea: put all 1s in the queue at distance 0 and spread outward.
• What if rot also spreads on a slant? Use 8 directions instead of 4. Nothing else changes.
• What if some oranges take 2 minutes to rot? Now steps have different costs, so a plain queue is not enough. Use Dijkstra with a priority queue, or a 0 and 1 trick with a deque when costs are only 0 or 1.
• Walls and gates: fill every empty room with its distance to the nearest gate. Again, all gates go in the queue first.

Remember this

Grown-up words: the crate is a grid graph, the ripples are levels of a breadth first search, starting from all rotten oranges together is multi source BFS, and the waiting line is a queue.