SyntaxPilot
Courses/DSA and Coding Problems/Lesson 49
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 49 of 90

Rotting oranges: multi-source BFS

queued

These are the notes for DSA episode 49. A grid holds empty cells, fresh oranges and rotten oranges; every minute, rot spreads from each rotten orange to the fresh oranges touching it. How many minutes until no fresh orange is left, or is that impossible? Last episode we counted islands with flood fill. Today BFS learns a new trick: starting from many places at once. We start from a real-life problem (a crate of mangoes in cold storage), define every word, try two obvious ideas (rotting oranges in place gives a wrong answer, and copying the grid every minute is correct but hits Time Limit Exceeded on a 400 × 400 grid), find the key insight (multi-source BFS: every rotten orange starts in the queue, and each BFS level is one minute), and finish with an O(rows × cols) solution. Every program below was run with javac 21 with an 8-second limit (like the SyntaxPilot compiler), and every output shown is real.

The problem, in real life

A crate of mangoes sits in a cold storage, packed neatly in rows and columns. One mango goes bad, and a bad mango spoils the mangoes touching it. So every day, the rot spreads one more step: up, down, left and right. Some places in the crate are empty, and an empty gap stops the rot. The shopkeeper wants to know: after how many days is every mango spoilt? Or will some mango stay safe forever?

In the crate In code
The crate, in rows and columns a grid int[][] g
An empty place 0
A good (fresh) mango 1
A bad (rotten) mango 2
One day one minute = one BFS level
All the bad mangoes spreading together multi-source BFS: all 2s start in the queue
A mango cut off by empty places a fresh orange that never rots → answer -1

Every word, from zero

  • Grid, cell (r, c): a table of rows and columns; cell (r, c) is row r, column c, counted from 0 (episode 48).
  • Fresh / rotten / empty: the three values 1, 2 and 0 of a cell.
  • 4-directional neighbours: up, down, left and right. Diagonals do not count.
  • Minute: one step of time. In one minute, every fresh orange touching an orange that was rotten at the start of that minute becomes rotten.
  • Simulation: copying the rules of the real world step by step in code.
  • In place: changing the data you are reading while you read it, instead of writing into a copy.
  • Queue: first in, first out, like a ticket-counter line. Java: ArrayDeque with add (to the back) and poll (from the front).
  • BFS (breadth-first search): explore everything 1 step away, then 2 steps, then 3, using a queue (episode 47).
  • Level: all the cells at the same distance from the start in a BFS. Here, the oranges that rot in the same minute.
  • Source: a starting point of a BFS.
  • Multi-source BFS: one BFS that starts with several sources in the queue at once. Each cell is reached first from its nearest source.
  • Freezing the queue size: for (int size = q.size(); size > 0; size--) reads the size once, so the loop takes exactly the cells of the current level, and cells added during the loop wait for the next level.

Problem statement

LeetCode 994, Rotting Oranges. You are given an m × n grid where each cell is:

  • 0: an empty cell,
  • 1: a fresh orange,
  • 2: 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 pass until no cell has a fresh orange. If this is impossible, return -1.

Grid (rows) Answer Why
211 / 110 / 011 4 the rot reaches the bottom-right orange in minute 4
211 / 011 / 101 -1 the orange at the bottom left is cut off by empty cells
02 0 there is no fresh orange at all

Constraints on LeetCode: 1 ≤ m, n ≤ 10. We will also test a 400 × 400 grid, because a real warehouse is big and interviewers like to ask "what if the grid were huge?".

Example 1, minute by minute (2 = rotten):

minute 0    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

All programs below use this helper to write a grid as strings:

    static int[][] grid(String... rows) {
        int[][] g = new int[rows.length][];
        for (int i = 0; i < rows.length; i++) g[i] = rows[i].chars().map(ch -> ch - '0').toArray();
        return g;
    }

rows[i].chars() gives the character codes of the string, and ch - '0' turns the character '2' into the number 2.

Obvious idea 1: simulate it, in place

One minute = one pass over the whole grid. In the pass, every fresh orange that touches a rotten one becomes 2. Stop when a whole pass changes nothing. Then, if any fresh orange is left, return -1, else the number of minutes.

import java.util.*;

public class Main {
    static int[][] grid(String... rows) {
        int[][] g = new int[rows.length][];
        for (int i = 0; i < rows.length; i++) g[i] = rows[i].chars().map(ch -> ch - '0').toArray();
        return g;
    }
    static boolean touchesRotten(int[][] g, int r, int c) {
        int[][] d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int[] k : d) {
            int y = r + k[0], x = c + k[1];
            if (y >= 0 && x >= 0 && y < g.length && x < g[0].length && g[y][x] == 2) return true;
        }
        return false;
    }
    static int orangesRotting(int[][] g) {
        int minutes = 0;
        while (true) {
            boolean changed = false;
            for (int r = 0; r < g.length; r++)
                for (int c = 0; c < g[0].length; c++)
                    if (g[r][c] == 1 && touchesRotten(g, r, c)) { g[r][c] = 2; changed = true; }
            if (!changed) break;
            minutes++;
        }
        for (int[] row : g) for (int v : row) if (v == 1) return -1;
        return minutes;
    }
    public static void main(String[] args) {
        System.out.println(orangesRotting(grid("211", "110", "011")));
        System.out.println(orangesRotting(grid("211", "011", "101")));
        System.out.println(orangesRotting(grid("02")));
    }
}

Output:

1
-1
0

1 instead of 4. The other two answers are right, but the first is wrong.

Why it is wrong

During the pass for minute 1, (0,1) touches the rotten corner and rots. Fine. Then the scan reaches (0,2): it touches (0,1), which rotted a moment ago, in this same minute, so it rots too. In real life that takes another minute. The new rot keeps running ahead of the scan, and one single pass rots the whole connected group. The rule says a fresh orange rots only if it touches an orange that was rotten at the start of the minute.

Obvious idea 2: copy the grid every minute

Fix: every minute, copy the grid into next. Decide by reading the old grid g, but write the new rot into next. At the end of the minute, g = next.

import java.util.*;

public class Main {
    static int[][] grid(String... rows) {
        int[][] g = new int[rows.length][];
        for (int i = 0; i < rows.length; i++) g[i] = rows[i].chars().map(ch -> ch - '0').toArray();
        return g;
    }
    static boolean touchesRotten(int[][] g, int r, int c) {
        int[][] d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        for (int[] k : d) {
            int y = r + k[0], x = c + k[1];
            if (y >= 0 && x >= 0 && y < g.length && x < g[0].length && g[y][x] == 2) return true;
        }
        return false;
    }
    static int orangesRotting(int[][] g) {
        int minutes = 0;
        while (true) {
            int[][] next = new int[g.length][];
            for (int r = 0; r < g.length; r++) next[r] = g[r].clone();
            boolean changed = false;
            for (int r = 0; r < g.length; r++)
                for (int c = 0; c < g[0].length; c++)
                    if (g[r][c] == 1 && touchesRotten(g, r, c)) { next[r][c] = 2; changed = true; }
            if (!changed) break;
            g = next; minutes++;
        }
        for (int[] row : g) for (int v : row) if (v == 1) return -1;
        return minutes;
    }
    public static void main(String[] args) {
        System.out.println(orangesRotting(grid("211", "110", "011")));
        System.out.println(orangesRotting(grid("211", "011", "101")));
        System.out.println(orangesRotting(grid("02")));
    }
}

Output:

4
-1
0

Correct now: 4, -1 and 0.

A 400 × 400 warehouse: Time Limit Exceeded

The fresh oranges form one long snake: every even row is full, and the odd rows join them at alternating ends. A single rotten orange sits in the top-left corner.

        int n = 400;
        int[][] g = new int[n][n];
        for (int r = 0; r < n; r++) {
            if (r % 2 == 0) Arrays.fill(g[r], 1);
            else g[r][(r / 2) % 2 == 0 ? n - 1 : 0] = 1;
        }
        g[0][0] = 2;
        long t0 = System.nanoTime();
        int m = orangesRotting(g);
        System.out.println(m + " minutes, " + (System.nanoTime() - t0) / 1000000 + " ms");
(no output: Time Limit Exceeded after 8 seconds)

Why it is slow

The snake is about 80,000 oranges long, and the rot moves one orange per minute, so the answer is about 80,000 minutes. Every minute we copy and scan all 1,60,000 cells. That is about 80,000 × 1,60,000 ≈ 1,300 crore steps. In general, with R rows and C columns, the answer can be close to R × C minutes, and each costs R × C: O((R × C)²). The waste is obvious: in each pass only one or two oranges change, yet we look at every cell.

What if, each minute, we only looked at the oranges that just rotted?

The key insight: multi-source BFS

Remember the stone in a pond from episode 47: BFS spreads ring by ring, like ripples. Now drop many stones at the same moment.

In a pond In the grid
Drop many stones at once put every rotten orange in the queue at minute 0
All ripples grow together, one ring per second one BFS level = one minute
A ring is just the newest ripple a level is exactly the oranges that rotted last minute
Each spot is hit first by the nearest stone each orange rots once, at its distance from the nearest rotten orange

Why must all sources start together? Take the row 2 1 1 1 1 1 2. If BFS started from the left 2 only, the last orange would rot at minute 5. With both rotten oranges in the queue at minute 0, the rot spreads from both ends and meets in the middle at minute 3.

minute 0:  2 1 1 1 1 1 2
minute 1:  2 2 1 1 1 2 2
minute 2:  2 2 2 1 2 2 2
minute 3:  2 2 2 2 2 2 2

The plan:

  1. Scan once: every 2 goes into the queue; count the fresh 1s.
  2. While fresh > 0 and the queue is not empty: minutes++.
  3. Take exactly q.size() cells (this minute's level).
  4. Each fresh neighbour: make it 2 now, fresh--, add it to the queue.
  5. At the end: fresh == 0 ? minutes : -1.

Marking a neighbour rotten the moment it is added means it can never be added twice.

The optimal solution in Java: multi-source BFS

import java.util.*;

public class Main {
    static int[][] grid(String... rows) {
        int[][] g = new int[rows.length][];
        for (int i = 0; i < rows.length; i++) g[i] = rows[i].chars().map(ch -> ch - '0').toArray();
        return g;
    }
    static int orangesRotting(int[][] g) {
        int R = g.length, C = g[0].length, fresh = 0, minutes = 0;
        int[][] d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        Deque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++) {
                if (g[r][c] == 2) q.add(new int[]{r, c});
                else if (g[r][c] == 1) fresh++;
            }
        while (fresh > 0 && !q.isEmpty()) {
            minutes++;
            for (int size = q.size(); size > 0; size--) {
                int[] p = q.poll();
                for (int[] k : d) {
                    int y = p[0] + k[0], x = p[1] + k[1];
                    if (y >= 0 && x >= 0 && y < R && x < C && g[y][x] == 1) {
                        g[y][x] = 2; fresh--; q.add(new int[]{y, x});
                    }
                }
            }
        }
        return fresh == 0 ? minutes : -1;
    }
    public static void main(String[] args) {
        System.out.println(orangesRotting(grid("211", "110", "011")));
        System.out.println(orangesRotting(grid("211", "011", "101")));
        System.out.println(orangesRotting(grid("02")));
        System.out.println(orangesRotting(grid("0")));
        System.out.println(orangesRotting(grid("1")));
        System.out.println(orangesRotting(grid("2111112")));
    }
}

Output (the three examples; then no oranges, one fresh orange with nothing rotten, and the row with rotten oranges at both ends):

4
-1
0
0
-1
3

Line by line:

  • fresh counts the fresh oranges still waiting. It tells us when to stop and whether the answer is -1.
  • The first double loop puts all sources in the queue before the first minute starts.
  • while (fresh > 0 && !q.isEmpty()): stop as soon as nothing fresh is left (otherwise we would count an extra empty minute), or when the rot can't spread any more.
  • for (int size = q.size(); size > 0; size--) takes one level: the oranges that rotted in the previous minute.
  • g[y][x] = 2; fresh--; q.add(...) rots a neighbour once and schedules it for the next minute.

The snake in milliseconds

80199 minutes, 10 ms

80,199 minutes, computed in milliseconds: every orange rotted once and was looked at once.

The same solution in C++

#include <bits/stdc++.h>
using namespace std;

int orangesRotting(vector<vector<int>> g) {
    int R = g.size(), C = g[0].size(), fresh = 0, minutes = 0;
    int d[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    queue<pair<int, int>> q;
    for (int r = 0; r < R; r++)
        for (int c = 0; c < C; c++) {
            if (g[r][c] == 2) q.push({r, c});
            else if (g[r][c] == 1) fresh++;
        }
    while (fresh > 0 && !q.empty()) {
        minutes++;
        for (int size = q.size(); size > 0; size--) {
            auto [pr, pc] = q.front(); q.pop();
            for (auto& k : d) {
                int y = pr + k[0], x = pc + k[1];
                if (y >= 0 && x >= 0 && y < R && x < C && g[y][x] == 1) {
                    g[y][x] = 2; fresh--; q.push({y, x});
                }
            }
        }
    }
    return fresh == 0 ? minutes : -1;
}

int main() {
    cout << orangesRotting({{2, 1, 1}, {1, 1, 0}, {0, 1, 1}}) << "\n";   // 4
    cout << orangesRotting({{2, 1, 1}, {0, 1, 1}, {1, 0, 1}}) << "\n";   // -1
    cout << orangesRotting({{0, 2}}) << "\n";                            // 0
    cout << orangesRotting({{2, 1, 1, 1, 1, 1, 2}}) << "\n";             // 3
}
4
-1
0
3

The same solution in Python

from collections import deque

def oranges_rotting(grid):
    g = [row[:] for row in grid]          # don't change the caller's grid
    R, C = len(g), len(g[0])
    q = deque((r, c) for r in range(R) for c in range(C) if g[r][c] == 2)
    fresh = sum(row.count(1) for row in g)
    minutes = 0
    while fresh > 0 and q:
        minutes += 1
        for _ in range(len(q)):           # exactly this minute's level
            r, c = q.popleft()
            for y, x in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
                if 0 <= y < R and 0 <= x < C and g[y][x] == 1:
                    g[y][x] = 2
                    fresh -= 1
                    q.append((y, x))
    return minutes if fresh == 0 else -1

print(oranges_rotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]))   # 4
print(oranges_rotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]]))   # -1
print(oranges_rotting([[0, 2]]))                            # 0
print(oranges_rotting([[2, 1, 1, 1, 1, 1, 2]]))             # 3
4
-1
0
3

The Python version copies the grid first ([row[:] for row in grid]) so the caller's grid is not changed. for _ in range(len(q)) freezes the level size just like the Java loop.

Two real bugs

Bug 1: looping only while the queue is not empty

import java.util.*;

public class Main {
    static int[][] grid(String... rows) {
        int[][] g = new int[rows.length][];
        for (int i = 0; i < rows.length; i++) g[i] = rows[i].chars().map(ch -> ch - '0').toArray();
        return g;
    }
    static int orangesRotting(int[][] g) {
        int R = g.length, C = g[0].length, fresh = 0, minutes = 0;
        int[][] d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        Deque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++) {
                if (g[r][c] == 2) q.add(new int[]{r, c});
                else if (g[r][c] == 1) fresh++;
            }
        while (!q.isEmpty()) {
            minutes++;
            for (int size = q.size(); size > 0; size--) {
                int[] p = q.poll();
                for (int[] k : d) {
                    int y = p[0] + k[0], x = p[1] + k[1];
                    if (y >= 0 && x >= 0 && y < R && x < C && g[y][x] == 1) {
                        g[y][x] = 2; fresh--; q.add(new int[]{y, x});
                    }
                }
            }
        }
        return fresh == 0 ? minutes : -1;
    }
    public static void main(String[] args) {
        System.out.println(orangesRotting(grid("211", "110", "011")));
        System.out.println(orangesRotting(grid("211", "011", "101")));
        System.out.println(orangesRotting(grid("02")));
    }
}
5
-1
1

5 instead of 4, and 1 instead of 0. The oranges that rotted in the last minute are still in the queue, so the loop runs one more minute in which nothing rots. In the third example there is no fresh orange at all, but the rotten one is in the queue, so it counts a minute. Fix: while (fresh > 0 && !q.isEmpty()).

Bug 2: returning the minutes without checking for leftovers

import java.util.*;

public class Main {
    static int[][] grid(String... rows) {
        int[][] g = new int[rows.length][];
        for (int i = 0; i < rows.length; i++) g[i] = rows[i].chars().map(ch -> ch - '0').toArray();
        return g;
    }
    static int orangesRotting(int[][] g) {
        int R = g.length, C = g[0].length, fresh = 0, minutes = 0;
        int[][] d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        Deque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++) {
                if (g[r][c] == 2) q.add(new int[]{r, c});
                else if (g[r][c] == 1) fresh++;
            }
        while (fresh > 0 && !q.isEmpty()) {
            minutes++;
            for (int size = q.size(); size > 0; size--) {
                int[] p = q.poll();
                for (int[] k : d) {
                    int y = p[0] + k[0], x = p[1] + k[1];
                    if (y >= 0 && x >= 0 && y < R && x < C && g[y][x] == 1) {
                        g[y][x] = 2; fresh--; q.add(new int[]{y, x});
                    }
                }
            }
        }
        return minutes;
    }
    public static void main(String[] args) {
        System.out.println(orangesRotting(grid("211", "110", "011")));
        System.out.println(orangesRotting(grid("211", "011", "101")));
        System.out.println(orangesRotting(grid("02")));
    }
}
4
5
0

5 instead of -1 for the second example. The orange in the bottom-left corner never rots, but the queue simply ran dry and we returned the minutes counted so far. Fix: return fresh == 0 ? minutes : -1;.

Complexity

Approach Time Space 400 × 400 snake
Rot in place O((R × C)²) O(1) (wrong answer anyway)
Copy the grid every minute O((R × C)²) O(R × C) for the copy Time Limit Exceeded
BFS from each fresh orange to the nearest rotten one O((R × C)²) O(R × C) far too slow (not run)
Multi-source BFS O(R × C) O(R × C) for the queue milliseconds

Multi-source BFS scans the grid once, every orange enters the queue at most once, and each one checks 4 neighbours. You must look at every cell at least once, so O(R × C) is the best possible.

Common mistakes

Mistake What you see (real) Why Fix
Rotting in place during the scan 1 instead of 4 new rot spreads in the same minute BFS levels (or write into a copy)
while (!q.isEmpty()) only 5 instead of 4, 1 instead of 0 counts a last, empty minute while (fresh > 0 && !q.isEmpty())
return minutes; 5 instead of -1 unreachable fresh oranges ignored fresh == 0 ? minutes : -1
BFS from one rotten orange only 5 instead of 3 on 2111112 the other sources start late put every source in the queue first

Mini project: the cold-storage spoilage report

Read a crate as text (2 bad, 1 good, . empty), print the day each mango spoils, the last day, and the mangoes that stay safe forever (S). It is the same multi-source BFS, storing the day in an array instead of counting minutes.

import java.util.*;

public class Main {
    // Mini project: the cold-storage spoilage report. Reads a crate as text (2 = bad, 1 = good, . = empty),
    // prints the day each mango spoils, the last day, and the mangoes that stay safe.
    public static void main(String[] args) {
        String[] crate = {"2111.", "11.11", "...11", "11..2", "1...."};
        int R = crate.length, C = crate[0].length();
        int[][] day = new int[R][C];
        Deque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++) {
                day[r][c] = crate[r].charAt(c) == '2' ? 0 : -1;
                if (crate[r].charAt(c) == '2') q.add(new int[]{r, c});
            }
        int[][] d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int last = 0;
        while (!q.isEmpty()) {
            int[] p = q.poll();
            for (int[] k : d) {
                int y = p[0] + k[0], x = p[1] + k[1];
                if (y >= 0 && x >= 0 && y < R && x < C && crate[y].charAt(x) == '1' && day[y][x] == -1) {
                    day[y][x] = day[p[0]][p[1]] + 1;
                    last = Math.max(last, day[y][x]);
                    q.add(new int[]{y, x});
                }
            }
        }
        List<String> safe = new ArrayList<>();
        for (int r = 0; r < R; r++) {
            StringBuilder sb = new StringBuilder();
            for (int c = 0; c < C; c++) {
                char ch = crate[r].charAt(c);
                if (ch == '.') sb.append("  .");
                else if (day[r][c] == -1) { sb.append("  S"); safe.add("(" + r + "," + c + ")"); }
                else sb.append(String.format("%3d", day[r][c]));
            }
            System.out.println(sb);
        }
        System.out.println("Last mango spoils on day " + last);
        System.out.println("Safe forever: " + safe);
    }
}
  0  1  2  3  .
  1  2  .  3  2
  .  .  .  2  1
  S  S  .  .  0
  S  .  .  .  .
Last mango spoils on day 3
Safe forever: [(3,0), (3,1), (4,0)]

Practice

1. 01 Matrix (LeetCode 542). For every cell of a 0/1 matrix, find the distance to the nearest 0.

Solution

Every 0 is a source. Multi-source BFS from all of them; the first time a cell is reached, its distance is final.

import java.util.*;

public class Main {
    // 01 Matrix (LeetCode 542): distance of every cell to the nearest 0. Every 0 is a source.
    static int[][] updateMatrix(int[][] mat) {
        int R = mat.length, C = mat[0].length;
        int[][] dist = new int[R][C];
        int[][] d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        Deque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++) {
                if (mat[r][c] == 0) q.add(new int[]{r, c});
                else dist[r][c] = -1;                 // -1 = not reached yet
            }
        while (!q.isEmpty()) {
            int[] p = q.poll();
            for (int[] k : d) {
                int y = p[0] + k[0], x = p[1] + k[1];
                if (y >= 0 && x >= 0 && y < R && x < C && dist[y][x] == -1) {
                    dist[y][x] = dist[p[0]][p[1]] + 1;
                    q.add(new int[]{y, x});
                }
            }
        }
        return dist;
    }
    public static void main(String[] args) {
        int[][] mat = {{0, 0, 0}, {0, 1, 0}, {1, 1, 1}};
        for (int[] row : updateMatrix(mat)) System.out.println(Arrays.toString(row));
    }
}
[0, 0, 0]
[0, 1, 0]
[1, 2, 1]

2. Print each orange's rotting minute. Instead of one number, print the minute at which every orange rots (-1 = never, . = empty).

Solution
import java.util.*;

public class Main {
    // Print the minute at which every orange rots (-1 = never, '.' = empty cell).
    static int[][] rotMinute(int[][] g) {
        int R = g.length, C = g[0].length;
        int[][] when = new int[R][C];
        int[][] d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        Deque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < R; r++)
            for (int c = 0; c < C; c++) {
                when[r][c] = g[r][c] == 2 ? 0 : -1;
                if (g[r][c] == 2) q.add(new int[]{r, c});
            }
        while (!q.isEmpty()) {
            int[] p = q.poll();
            for (int[] k : d) {
                int y = p[0] + k[0], x = p[1] + k[1];
                if (y >= 0 && x >= 0 && y < R && x < C && g[y][x] == 1 && when[y][x] == -1) {
                    when[y][x] = when[p[0]][p[1]] + 1;
                    q.add(new int[]{y, x});
                }
            }
        }
        return when;
    }
    public static void main(String[] args) {
        int[][] g = {{2, 1, 1}, {0, 1, 1}, {1, 0, 1}};
        int[][] w = rotMinute(g);
        for (int r = 0; r < g.length; r++) {
            StringBuilder sb = new StringBuilder();
            for (int c = 0; c < g[0].length; c++) sb.append(g[r][c] == 0 ? " ." : String.format("%2d", w[r][c]));
            System.out.println(sb);
        }
    }
}
 0 1 2
 . 2 3
-1 . 4

The largest number is the answer to LeetCode 994; any -1 on an orange means the answer is -1.

3. As Far from Land as Possible (LeetCode 1162). In an n × n grid of land (1) and water (0), find the water cell whose distance to the nearest land is as large as possible (-1 if there is no land or no water).

Solution

Every land cell is a source. The last level BFS reaches is the answer.

import java.util.*;

public class Main {
    // As Far from Land as Possible (LeetCode 1162): the water cell farthest from any land. Every land cell is a source.
    static int maxDistance(int[][] g) {
        int n = g.length, best = -1;
        int[][] dist = new int[n][n];
        int[][] d = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        Deque<int[]> q = new ArrayDeque<>();
        for (int r = 0; r < n; r++)
            for (int c = 0; c < n; c++) {
                dist[r][c] = g[r][c] == 1 ? 0 : -1;
                if (g[r][c] == 1) q.add(new int[]{r, c});
            }
        if (q.isEmpty() || q.size() == n * n) return -1;   // no land, or no water
        while (!q.isEmpty()) {
            int[] p = q.poll();
            for (int[] k : d) {
                int y = p[0] + k[0], x = p[1] + k[1];
                if (y >= 0 && x >= 0 && y < n && x < n && dist[y][x] == -1) {
                    dist[y][x] = dist[p[0]][p[1]] + 1;
                    best = Math.max(best, dist[y][x]);
                    q.add(new int[]{y, x});
                }
            }
        }
        return best;
    }
    public static void main(String[] args) {
        System.out.println(maxDistance(new int[][]{{1, 0, 1}, {0, 0, 0}, {1, 0, 1}}));   // 2
        System.out.println(maxDistance(new int[][]{{1, 0, 0}, {0, 0, 0}, {0, 0, 0}}));   // 4
    }
}
2
4

4. Walls and Gates. A grid has walls (-1), gates (0) and empty rooms (∞). Fill each room with the distance to its nearest gate.

Solution

Exactly practice 1 with different symbols: put every gate in the queue at the start, never step into a wall, and write dist + 1 into each room the first time BFS reaches it. Time O(rows × cols). Running a separate BFS from each gate would be O(gates × rows × cols).

Quick quiz

2 1 1 1
1 1 0 1
0 0 1 2

How many minutes until every orange is rotten? A) 2 B) 3 C) 4 D) -1

Answer

A) 2. Both rotten oranges start together. Minute 1: (0,1), (1,0), (1,3), (2,2). Minute 2: (0,2), (1,1), (0,3). Nothing fresh is left after minute 2.

Interview questions

  1. Why does every rotten orange go into the queue before the first minute? Because they all start spreading at the same time. Each fresh orange must rot at its distance from the nearest rotten orange; starting all sources together gives exactly that (a multi-source BFS is the same as a BFS from one imaginary "super source" joined to every rotten orange).
  2. How do you know where one minute ends in the queue? Freeze the size: for (int size = q.size(); ...). Or store the minute with each cell ({r, c, minute}) and keep the largest.
  3. When do you return -1? When the BFS ends and fresh > 0: some fresh orange had no path of oranges to any rotten one.
  4. Can you do it without changing the input grid? Yes: keep a separate int[][] when (or boolean[][] seen) array, as in practice 2. Same complexity.
  5. Why not run a BFS from each fresh orange to its nearest rotten one? Correct, but O((R × C)²) in the worst case. One multi-source BFS answers all of them at once in O(R × C).
  6. What is the time and space complexity? O(R × C) time; O(R × C) space for the queue in the worst case.

Glossary

Term Meaning
Grid A table of rows and columns; here int[][]
Cell (r, c) The square in row r, column c, counted from 0
Fresh / rotten / empty Cell values 1, 2, 0
4-directional neighbours The cells up, down, left and right (no diagonals)
Minute One step of time; one BFS level
Simulation Copying the real-world rules step by step in code
In place Changing the data while you are still reading it
Queue First in, first out; ArrayDeque with add and poll
BFS Breadth-first search: explore by distance, ring by ring, with a queue
Level All cells at the same BFS distance; the oranges rotting in the same minute
Source A starting point of a BFS
Multi-source BFS One BFS with many sources in the queue at the start
Super source An imaginary vertex joined to every source; a multi-source BFS is a normal BFS from it
Freezing the size Reading q.size() once so a loop takes exactly one level
Time Limit Exceeded The program ran longer than the allowed time (8 s here)
O(R × C) Time that grows with the number of cells

Summary

  • Rotting in place lets the rot run ahead of the clock: 1 instead of 4.
  • Copying the grid every minute is correct but O((R × C)²): Time Limit Exceeded on a 400 × 400 snake.
  • Multi-source BFS: put every rotten orange in the queue first; each BFS level is one minute; freeze q.size() to take one level.
  • Mark an orange rotten when you add it, count the fresh ones, and return -1 if any are left.
  • O(R × C) time and space.
  • Next episode: cycle detection in undirected and directed graphs.