Start learning free

LESSON 477 OF 541 · GRAPHS

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

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

    SWIFT · GRAPHS

    Rotting Oranges in Swift, explained

    Problem overview

    The function orangesRotting(_ grid: [[Int]]) -> Int receives a grid of m rows and n columns. Each cell is 0 (empty), 1 (a fresh orange) or 2 (a rotten orange). Every minute, each fresh orange that touches a rotten one up, down, left or right (not diagonally) becomes rotten. The function returns the number of minutes until no fresh orange is left, or -1 if some orange can never rot.

    Take this grid:

    2 1 1
1 1 0
0 1 1

    The grid after each minute is below. After minute 4 no cell is fresh, so the answer is 4.

    minute 1   minute 2   minute 3   minute 4
2 2 1      2 2 2      2 2 2      2 2 2
2 1 0      2 2 0      2 2 0      2 2 0
0 1 1      0 1 1      0 2 1      0 2 2

    If the grid has no fresh orange at the start, as in [[0, 2]], no time has to pass and the answer is 0. In [[2, 1, 1], [0, 1, 1], [1, 0, 1]] the orange in the bottom left corner has empty cells above it and to its right. Rot doesn't spread diagonally, so it stays fresh and the answer is -1.

    Approach: breadth-first search from every rotten orange

    The direct way is to simulate: each minute, scan the whole grid and rot the fresh oranges next to rotten ones. That can cost O((m · n)²) time. A long winding line of oranges that the rot creeps along one cell per minute needs about m · n minutes, and each minute scans m · n cells.

    A breadth-first search (BFS) does the same thing without the rescans. Think of the rotten oranges as the sources of a wave. The oranges that rot in minute 1 are the first level of the search, the oranges those rot in minute 2 are the second level, and so on. The number of levels is the number of minutes. Since oranges that are rotten at the start all spread the rot at the same time, the search starts from all of them at once, with all of them in the queue.

    Two more ideas finish the job. A counter of fresh oranges, lowered each time one rots, tells at the end whether some orange never rotted: if it is still above 0, the answer is -1. And marking an orange as rotten the moment it is queued means each cell joins the queue at most once.

    Step by step

    1. Copy the grid into a variable with var grid = grid. Swift parameters are constants, and the search marks oranges as rotten. The copy has the same name, so the rest of the function uses it.
    2. Store the sizes: rows is grid.count and cols is grid[0].count. Every row has the same length.
    3. Create queue as an empty array of (Int, Int) tuples. It holds (row, column) pairs for the oranges that are about to spread the rot.
    4. Create fresh starting at 0, the count of fresh oranges.
    5. Scan every cell with two nested loops over 0..<rows and 0..<cols.
    6. Queue each rotten orange (a 2), because all of them spread the rot in the first minute.
    7. Count each fresh orange (a 1) in fresh. Empty cells are neither.
    8. Define directions, the four moves as (row change, column change) tuples. Each move changes only the row or only the column, so diagonal cells are never neighbours.
    9. Create minutes starting at 0. If nothing is fresh, no time passes.
    10. Create head starting at 0, the index of the next orange to take from queue. Moving an index forward takes oranges from the front without removing anything. Removing the first element of an array would shift all the others each time.
    11. Loop while head < queue.count && fresh > 0. Each turn is one minute. Without the fresh > 0 part, the loop would count one extra minute after the last orange rots.
    12. Add 1 to minutes at the start of the turn.
    13. Remember where this minute ends: levelEnd is queue.count. The oranges from head up to levelEnd spread the rot in this minute. Oranges added during the minute land past levelEnd and wait for the next one.
    14. Loop while head < levelEnd. One pass of this loop handles one level of the BFS.
    15. Take the orange at head as let (row, col) = queue[head], then move head forward by 1.
    16. Loop over directions with (dr, dc) and compute nextRow and nextCol.
    17. Check the neighbour: it must be inside the grid and hold a fresh orange. The bounds come first in the condition, so the grid is only read for a cell that exists.
    18. Rot it: set it to 2, subtract 1 from fresh and append it to the queue. Marking it right away stops any other orange from rotting it again or queueing it twice.
    19. After the loops, return -1 if fresh > 0: the queue ran out while some oranges were still fresh, so no chain of oranges links them to a rotten one.
    20. Otherwise return minutes.

    The solution in Swift

    class Solution {
    func orangesRotting(_ grid: [[Int]]) -> Int {
        var grid = grid
        let rows = grid.count
        let cols = grid[0].count
        var queue = [(Int, Int)]()
        var fresh = 0
        for r in 0..<rows {
            for c in 0..<cols {
                if grid[r][c] == 2 {
                    queue.append((r, c))
                }
                if grid[r][c] == 1 {
                    fresh += 1
                }
            }
        }
        let directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        var minutes = 0
        var head = 0
        while head < queue.count && fresh > 0 {
            minutes += 1
            let levelEnd = queue.count
            while head < levelEnd {
                let (row, col) = queue[head]
                head += 1
                for (dr, dc) in directions {
                    let nextRow = row + dr
                    let nextCol = col + dc
                    if nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols && grid[nextRow][nextCol] == 1 {
                        grid[nextRow][nextCol] = 2
                        fresh -= 1
                        queue.append((nextRow, nextCol))
                    }
                }
            }
        }
        if fresh > 0 {
            return -1
        }
        return minutes
    }
}

    The Swift details worth a closer look:

    • var grid = grid. A function parameter is a constant, but a new local variable can reuse the name. Arrays are value types, so the copy is independent: the search changes its own grid and the caller's array stays as it was.
    • Tuples in arrays. [(Int, Int)]() is an empty array of pairs. queue.append((r, c)) needs the double parentheses: the outer ones are the call, the inner ones build the tuple. let (row, col) = queue[head] unpacks a pair into two constants, and for (dr, dc) in directions does the same in the loop header. The compiler infers the type of directions as [(Int, Int)].
    • && short-circuits. It stops at the first false part. That is why the four bounds checks come before grid[nextRow][nextCol]: an index outside the array would stop the program with a run-time error.
    • Why head and not removeFirst(). queue.removeFirst() is O(n), because it shifts every remaining element. The array only grows, and head marks how far the search has got. The queue holds at most one entry per cell.
    • 0..<rows. This half-open range covers rows 0 to rows - 1. The lesson guarantees at least one row, so grid[0] exists.

    Complexity

    Time: O(m · n). The first scan visits each cell once. In the search, each cell joins the queue at most once, and each queued cell looks at its 4 neighbours, which is constant work.

    Space: O(m · n). The copy of the grid takes m · n numbers, and the queue holds at most one entry per cell.

    Edge cases and common mistakes

    • No fresh oranges. [[0, 2]], [[0]] and [[2]] all give 0, because fresh is 0 and the loop never starts.
    • Fresh oranges but no rotten one. [[1]] gives -1: the queue is empty, so the loop doesn't run and fresh is still 1.
    • Unreachable oranges. [[1, 0, 2]] gives -1, since the empty cell blocks the rot. [[2, 0], [0, 1]] gives -1 too, because diagonal cells aren't neighbours.
    • An extra minute. Without && fresh > 0 in the loop condition, the last wave of rotten oranges is still in the queue after the final orange rots, and one more minute is counted. [[1, 2]] would give 2 instead of 1, and [[2, 1, 1]] would give 3 instead of 2.
    • Several rotten oranges at the start. [[2, 1], [1, 2]] gives 1: both fresh oranges are next to a rotten one. Starting the search from one source at a time would give a larger count.
    • Marking too late. If an orange is marked only when taken from the queue, a neighbour of two rotten oranges can be queued twice, and fresh goes wrong.
    • Counting minutes per orange. Minutes must be counted per level, not per queue entry. The levelEnd bound is what separates one minute from the next.

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