Start learning free

LESSON 475 OF 539 · GRAPHS

Rotting Oranges in C#: Multi-Source BFS in O(m · n)

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 22
    Ctrl + Enter to check

    C# · GRAPHS

    Rotting Oranges in C#, explained

    Problem overview

    The method OrangesRotting receives a grid as a jagged array, int[][] grid. Each cell is 0 (empty), 1 (a fresh orange) or 2 (a rotten orange). Every minute, each fresh orange that touches a rotten one above, below, left or right becomes rotten. Diagonal contact doesn't count. The method returns the number of minutes until no fresh orange is left, or -1 if some orange can never rot.

    In the first example, the grid {{2,1,1},{1,1,0},{0,1,1}} takes 4 minutes: the rot travels outward from the corner one step per minute, and the bottom-right orange is the last to turn. In the second example, {{2,1,1},{0,1,1},{1,0,1}}, the orange in the bottom-left corner has empty cells above and to its right, so nothing reaches it, and the answer is -1. For {{0,2}} there is no fresh orange, so the answer is 0.

    The lesson asks for O(m · n) time and space for an m by n grid.

    Approach: spread the rot level by level

    The direct simulation scans the whole grid every minute. On a long winding line of oranges that the rot creeps along one cell per minute, the number of minutes is proportional to the number of cells, so the total is quadratic in the grid size.

    A breadth-first search (BFS) is a better fit, because breadth-first order is exactly the order in which the rot spreads. Start with all the rotten oranges in a queue at once, since they all begin spreading in minute 1. The oranges that rot in minute 1 form the first level, the oranges they rot form the second level, and so on. The number of levels processed is the number of minutes.

    Two more pieces finish the job:

    • A counter fresh holds the number of fresh oranges and goes down each time one rots. If it is still above 0 when the queue runs out, no chain of oranges connects those oranges to a rotten one, and the answer is -1.
    • Rotting an orange immediately, by writing 2 into its cell, makes sure it is queued only once. Each cell enters the queue at most once and looks at four neighbours, which gives O(m · n) work.

    The loop condition also includes fresh > 0. Without it, the loop would count one more minute after the last orange rots, while the final rotten oranges look for fresh neighbours that no longer exist. On the first example, that version returns 5 instead of 4, and on {{2,1}} it returns 2 instead of 1.

    Step by step

    1. Store the grid's size. rows is grid.Length and cols is grid[0].Length, the length of the first row, since every row has the same length.
    2. Create the queue, a Queue<(int, int)> of (row, column) tuples. It holds the rotten oranges that are about to spread the rot.
    3. Create fresh, starting at 0.
    4. Scan every cell with two nested loops, r over rows and c over columns. A cell equal to 2 is enqueued as (r, c), and a cell equal to 1 adds one to fresh. Empty cells are neither.
    5. Describe the four moves in directions, an array of (row change, column change) tuples: up, down, left and right. Each changes only the row or only the column, so diagonal neighbours are excluded.
    6. Create minutes, starting at 0. With no fresh orange at the start, 0 is the answer.
    7. Loop while the queue isn't empty and fresh is above 0. Each turn of the loop is one minute, so add one to minutes at the top.
    8. Record levelSize, the queue's current count. Those oranges spread the rot this minute. Oranges that rot during the minute join the same queue, but they act in the next minute, so the inner loop runs exactly levelSize times.
    9. Dequeue one orange and unpack the tuple into row and col.
    10. Visit the four neighbours with a foreach over directions, unpacking each move into dr and dc, and compute nextRow and nextCol.
    11. Check the neighbour: inside the grid and fresh. The bounds come first, and && stops at the first false part, so the grid is only read for cells that exist.
    12. Rot it: set the cell to 2, subtract one from fresh and enqueue (nextRow, nextCol).
    13. After the loop, return -1 if fresh is still above 0, and minutes otherwise.

    The solution in C#

    class Solution {
    public int OrangesRotting(int[][] grid) {
        int rows = grid.Length;
        int cols = grid[0].Length;
        Queue<(int, int)> queue = new Queue<(int, int)>();
        int fresh = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == 2) {
                    queue.Enqueue((r, c));
                }
                if (grid[r][c] == 1) {
                    fresh++;
                }
            }
        }
        (int, int)[] directions = { (-1, 0), (1, 0), (0, -1), (0, 1) };
        int minutes = 0;
        while (queue.Count > 0 && fresh > 0) {
            minutes++;
            int levelSize = queue.Count;
            for (int i = 0; i < levelSize; i++) {
                (int row, int col) = queue.Dequeue();
                foreach ((int dr, int dc) in directions) {
                    int nextRow = row + dr;
                    int nextCol = col + dc;
                    if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols && grid[nextRow][nextCol] == 1) {
                        grid[nextRow][nextCol] = 2;
                        fresh--;
                        queue.Enqueue((nextRow, nextCol));
                    }
                }
            }
        }
        if (fresh > 0) {
            return -1;
        }
        return minutes;
    }
}

    The C# details worth knowing:

    • Jagged arrays. int[][] is an array of arrays, indexed grid[r][c]. grid.Length counts the rows and grid[0].Length counts the columns. This differs from the rectangular int[,], which uses grid[r, c].
    • Tuples. (int, int) is a value tuple: two integers kept together. queue.Enqueue((r, c)) needs the double parentheses, one pair for the call and one for the tuple. (int row, int col) = queue.Dequeue(); deconstructs a tuple into two new variables.
    • Array initializer. (int, int)[] directions = { ... }; builds the array of tuples with no new, because the declared type gives the element type.
    • foreach with deconstruction. foreach ((int dr, int dc) in directions) unpacks every tuple as the loop goes. It is why the loop body can use dr and dc directly.
    • Queue<T>. It lives in System.Collections.Generic. Enqueue adds at the back, Dequeue removes from the front, and Count is a property. Dequeuing from an empty queue throws, but the loop condition prevents that.
    • The input is changed. The method writes 2 into the caller's grid, so every orange that could rot is rotten afterwards. Copy the grid first if the original is needed again.
    • Reading queue.Count once. levelSize is stored before the inner loop because the count changes as oranges are enqueued. Using queue.Count as the loop bound would mix levels together.

    Complexity

    Time: O(m · n). The first scan visits each cell once. In the search, each cell is enqueued at most once, since it turns rotten the moment it is enqueued, and each dequeue checks four neighbours with constant work. A 300 by 300 grid of fresh oranges with one rotten corner takes 598 minutes and runs instantly.

    Space: O(m · n). In the worst case the queue holds a large share of the cells, for example when most of the grid starts rotten.

    Edge cases and common mistakes

    • No fresh oranges. {{0,2}} and {{0}} both return 0. The loop never starts, because fresh is 0.
    • No rotten oranges but a fresh one. {{1}} returns -1: the queue is empty, so nothing can ever rot.
    • Several rotten sources. {{2,1,1,2}} returns 1, because both rotten oranges spread in the same minute. Starting from one source at a time would give a wrong, larger answer.
    • A blocked orange. {{2,0,1}} returns -1. An empty cell stops the spread, and the orange beyond it is never reached.
    • Counting the extra minute. Dropping fresh > 0 from the loop condition overcounts by one whenever every orange rots.
    • Diagonal spread. Adding diagonal moves to directions would rot oranges that the problem says stay fresh, such as the corner in the second example.
    • Not marking oranges when they are enqueued. If the cell is only marked when it is dequeued, the same orange can be queued several times, and fresh is decremented more than once for it.
    • Checking the grid before the bounds. Reading grid[nextRow][nextCol] first throws an IndexOutOfRangeException at the edges. Keep the bounds checks on the left of the && chain.

    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}} gives 4.
    • {{2,1,1,2}} gives 1.
    • {{2,0,1}} gives -1.
    Keep going with C#500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free