Start learning free

LESSON 476 OF 540 · GRAPHS

Rotting Oranges in Kotlin: 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 22
    Ctrl + Enter to check

    KOTLIN · GRAPHS

    Rotting Oranges in Kotlin, explained

    Problem overview

    The grid is an Array<IntArray> where 0 is an empty cell, 1 a fresh orange and 2 a rotten orange. Every minute, each fresh orange that touches a rotten one (up, down, left or right, never diagonally) becomes rotten. orangesRotting(grid) returns the number of minutes until no orange is fresh, or -1 if some orange never rots.

    Take the grid with rows 2 1 1, 1 1 0 and 0 1 1. The rot starts in the top left corner and spreads one step per minute. After minute 4 every orange is rotten, so the answer is 4. In the grid with rows 2 1 1, 0 1 1 and 1 0 1 the orange in the bottom left corner has empty cells above it and to its right, and rot does not cross diagonals, so the answer is -1. A grid with no fresh orange, such as [[0, 2]], needs 0 minutes.

    Approach

    You could simulate the grid minute by minute and scan every cell each time. That works, but a long winding line of oranges lets the rot creep one cell per minute, so the number of minutes can be proportional to the number of cells and the total work grows like (m · n)².

    Breadth-first search fits better. Think of each rotten orange as a source that spreads the rot to its neighbours. BFS visits cells level by level: the cells at distance 1 from the sources, then distance 2, and so on. The oranges that rot in minute 1 are the first level, the oranges they rot are the second level, so the number of levels is the number of minutes.

    There are many sources, so every orange that is rotten at minute 0 goes into the queue before the search begins. A counter of fresh oranges, lowered each time one rots, tells at the end whether some orange was never reached.

    Step by step

    1. Dimensions. rows is grid.size, and cols is grid[0].size (every row has the same length).
    2. Queue and counter. An empty ArrayDeque<Pair<Int, Int>>() will hold (row, column) pairs of rotten oranges that are about to spread the rot. A var fresh counts the fresh ones.
    3. First pass. Two nested loops over every cell. A 2 is added to the queue as Pair(r, c); a 1 adds one to fresh. Empty cells are ignored.
    4. Directions. An array of four Pairs, up, down, left and right. Each move changes only the row or only the column, so diagonal cells are never neighbours.
    5. Minutes. var minutes starts at 0.
    6. The loop. while (queue.isNotEmpty() && fresh > 0). Each turn is one minute, so it starts with minutes++. The condition fresh > 0 stops the loop as soon as the last orange rots, so no extra minute is counted.
    7. One level at a time. Read queue.size into levelSize and run the body repeat(levelSize). Oranges that rot during this minute join the back of the same queue, but they spread the rot only in the next minute, so this minute handles exactly the oranges that were in the queue when it started.
    8. Visit the neighbours. Take the front pair with removeFirst(), unpack it into (row, col), and for each (dr, dc) compute nextRow and nextCol. If the neighbour is on the grid and holds a fresh orange, set it to 2, subtract one from fresh and add it to the queue. Marking it at once means no other orange rots it a second time or queues it again.
    9. Answer. If fresh > 0 after the loop, the queue ran out with fresh oranges left: nothing links them to a rotten one, so return -1. Otherwise return minutes.

    The solution in Kotlin

    class Solution {
    fun orangesRotting(grid: Array<IntArray>): Int {
        val rows = grid.size
        val cols = grid[0].size
        val queue = ArrayDeque<Pair<Int, Int>>()
        var fresh = 0
        for (r in 0 until rows) {
            for (c in 0 until cols) {
                if (grid[r][c] == 2) {
                    queue.add(Pair(r, c))
                }
                if (grid[r][c] == 1) {
                    fresh++
                }
            }
        }
        val directions = arrayOf(Pair(-1, 0), Pair(1, 0), Pair(0, -1), Pair(0, 1))
        var minutes = 0
        while (queue.isNotEmpty() && fresh > 0) {
            minutes++
            val levelSize = queue.size
            repeat(levelSize) {
                val (row, col) = queue.removeFirst()
                for ((dr, dc) in directions) {
                    val nextRow = row + dr
                    val nextCol = col + dc
                    if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols && grid[nextRow][nextCol] == 1) {
                        grid[nextRow][nextCol] = 2
                        fresh--
                        queue.add(Pair(nextRow, nextCol))
                    }
                }
            }
        }
        if (fresh > 0) {
            return -1
        }
        return minutes
    }
}

    Kotlin details worth knowing:

    • Destructuring. A Pair unpacks into two names: val (row, col) = queue.removeFirst(), and for ((dr, dc) in directions) does the same for each move.
    • ArrayDeque as a queue. Without an import it is Kotlin's own ArrayDeque. add puts a cell at the back and removeFirst() takes the one at the front, both in O(1) (amortised for adding).
    • Bounds before the read. && stops at the first false part, so grid[nextRow][nextCol] is read only for a cell that exists. Reorder the conditions and a neighbour off the edge throws ArrayIndexOutOfBoundsException.
    • The grid is changed. The function writes 2 into the array it receives, so after the call that grid holds the final state. For the first example it becomes rows 222, 220, 022.
    • repeat(levelSize) { ... } runs its block that many times. The size is copied into levelSize first, because queue.size keeps changing while the block adds cells.

    Complexity

    Time: the first pass visits every cell once. In the search, each cell enters the queue at most once and looks at 4 neighbours, so the whole search is O(m · n).

    Space: in the worst case the queue holds a large part of the grid, so O(m · n) extra space.

    Edge cases and common mistakes

    • No fresh oranges. [[0, 2]] returns 0, and so does [[0]]: the loop never starts.
    • Fresh but no rotten. [[1]] returns -1: the queue is empty and fresh is 1.
    • Unreachable oranges. A fresh orange walled off by empty cells, as in the second example, keeps fresh above 0, so the answer is -1.
    • An extra minute. Without fresh > 0 in the loop condition, the last rotten oranges are processed in one more minute that rots nothing. The first example then returns 5 instead of 4, and [[0, 2]] returns 1 instead of 0.
    • Starting from one rotten orange at a time. The rot spreads from all of them at once, so they must all be in the queue before the first minute.
    • Not marking the neighbour. If the cell stays 1, another orange can rot it again, fresh goes wrong and the cell is queued twice.

    Testing

    Each grid is written row by row, with the result:

    211 / 110 / 011   gives 4
211 / 011 / 101   gives -1
02                gives 0
1                 gives -1
21111             gives 4
2101              gives -1
211 / 111 / 012   gives 2
    Keep going with Kotlin500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free