Start learning free

LESSON 472 OF 536 · GRAPHS

Rotting Oranges in Python: 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: a list of rows, where each row is a list 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

    PYTHON · GRAPHS

    Rotting Oranges in Python, explained

    Problem overview

    The function orangesRotting(grid) receives a grid of m rows and n columns, a list of lists of integers. A cell is 0 (empty), 1 (a fresh orange) or 2 (a rotten orange). Every minute, each fresh orange directly above, below, left or right of a rotten one becomes rotten; diagonal neighbours don't count. The function returns the number of minutes until no fresh orange is left, or -1 if some orange can never rot.

    Take [[2, 1, 1], [1, 1, 0], [0, 1, 1]]. The rotten orange in the corner infects the two oranges beside it in minute 1, those infect their neighbours in minute 2, and so on until minute 4, when the last orange, in the bottom right corner, rots. The answer is 4. For [[2, 1, 1], [0, 1, 1], [1, 0, 1]] the answer is -1: the orange at the bottom left has empty cells above and to its right, so rot never reaches it. For [[0, 2]] no orange is fresh from the start, so the answer is 0.

    Approach: breadth-first search from every rotten orange at once

    Simulating the grid minute by minute, scanning every cell each time, works but can be slow. A long winding line of oranges lets rot creep one cell per minute, so the number of minutes can grow with the number of cells, and each minute costs a full scan: up to O((m · n)²) in total. The target is O(m · n) time and space.

    Rot spreading one step per minute is exactly how breadth-first search (BFS) explores a graph, level by level. Here the cells are the nodes and side-by-side cells are neighbours. The one twist is that the search starts from all the rotten oranges together, since they all spread the rot in minute 1. The oranges they rot form the second level, those oranges' neighbours the third, and so on. The number of levels that rot something is the number of minutes.

    A counter of fresh oranges, lowered every time one rots, answers the second question. If it is still above zero when the queue runs out, some oranges had no path from a rotten one, and the answer is -1.

    Step by step

    1. Read the size. rows = len(grid) and cols = len(grid[0]). Every row has the same length, so the first row gives the number of columns.
    2. Create an empty deque named queue. It will hold the rotten oranges that are about to spread the rot, as (row, column) tuples. A deque removes from the front in constant time.
    3. Start fresh at 0. It counts the oranges that are still fresh. When it reaches 0, nothing is left to rot.
    4. Loop r over range(rows) and, inside it, c over range(cols). This first pass over the whole grid finds the starting oranges.
    5. If grid[r][c] == 2, append (r, c) to queue. Every orange that is rotten at the start goes in before the search begins.
    6. If grid[r][c] == 1, add 1 to fresh. Empty cells are neither: nothing ever happens to them.
    7. Create directions. The four moves as (row change, column change): (-1, 0) up, (1, 0) down, (0, -1) left, (0, 1) right. Each changes the row or the column by one, never both, so diagonals are not neighbours.
    8. Start minutes at 0. If nothing is fresh at the start, no time passes.
    9. Loop while queue and fresh > 0. Each turn is one minute. An empty deque counts as false, so queue alone tests that it has entries. Without fresh > 0 the loop would count one extra minute after the last orange rots, while the last rotten oranges look for neighbours that are no longer fresh.
    10. Add 1 to minutes and store levelSize = len(queue). These are the oranges that spread the rot in this minute. Oranges that rot during the minute join the same queue but must wait for the next one, so this minute handles exactly levelSize oranges.
    11. Loop levelSize times and take the front orange. row, col = queue.popleft() unpacks the tuple. Oranges leave in the order they rotted, so this minute's oranges come out before the ones they infect. The loop variable is _, the usual name for one that isn't used.
    12. Loop over directions as dr, dc and compute the neighbour. nextRow = row + dr and nextCol = col + dc. The neighbour may lie off the grid, so the next condition checks that before reading it.
    13. If the neighbour is inside the grid and fresh, rot it. The condition 0 <= nextRow < rows and 0 <= nextCol < cols and grid[nextRow][nextCol] == 1 checks the bounds first, because and stops at the first false part. Then set grid[nextRow][nextCol] = 2, subtract 1 from fresh and append (nextRow, nextCol) to queue. Marking it rotten at once means no other orange infects it again or queues it a second time.
    14. After the loop, return -1 if fresh > 0. The queue ran out while some oranges were still fresh: no chain of oranges links them to a rotten one.
    15. Otherwise return minutes.

    The solution in Python

    class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        queue = deque()
        fresh = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:
                    queue.append((r, c))
                if grid[r][c] == 1:
                    fresh += 1
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        minutes = 0
        while queue and fresh > 0:
            minutes += 1
            levelSize = len(queue)
            for _ in range(levelSize):
                row, col = queue.popleft()
                for dr, dc in directions:
                    nextRow = row + dr
                    nextCol = col + dc
                    if 0 <= nextRow < rows and 0 <= nextCol < cols and grid[nextRow][nextCol] == 1:
                        grid[nextRow][nextCol] = 2
                        fresh -= 1
                        queue.append((nextRow, nextCol))
        if fresh > 0:
            return -1
        return minutes

    The Python details:

    • deque. It comes from collections; in a file of your own, add from collections import deque (and from typing import List for the hint). popleft() takes constant time, while list.pop(0) shifts every element and would make the search slower.
    • Tuple unpacking. row, col = queue.popleft() and for dr, dc in directions both split a two-element tuple into names.
    • Chained comparison. 0 <= nextRow < rows checks both bounds at once. The bounds check matters because a negative index doesn't fail in Python: grid[-1] reads the last row, so the search would wrap around the grid edge and rot oranges that aren't neighbours. An index past the end raises IndexError.
    • The input changes. The function marks oranges rotten inside grid itself. After a call on the first example, the grid is [[2, 2, 2], [2, 2, 0], [0, 2, 2]]. Copy the grid first if the caller needs the original.

    Complexity

    The first pass visits every cell once, O(m · n). In the search, each cell joins the queue at most once, because it is marked rotten when it is added, and each queued cell looks at four neighbours, so the search is O(m · n) too. The queue can hold up to O(m · n) cells, and that is the extra space.

    Edge cases and common mistakes

    • No fresh orange. [[0, 2]] gives 0, and so do [[0]] and [[2, 2]]. The while loop never starts, and fresh is 0.
    • A fresh orange and no rotten one. [[1]] gives -1. The queue is empty from the start, fresh stays 1, and the final check returns -1.
    • Unreachable oranges. A fresh orange walled in by empty cells or the grid's edge never rots, which is what the fresh counter detects. Diagonal contact does not count.
    • Counting one minute too many. Loop on while queue alone and the last level of rotten oranges takes one more turn that rots nothing, so the answer comes out one too big. The fresh > 0 condition prevents that.
    • Not processing one level at a time. Popping oranges without fixing levelSize first mixes this minute's oranges with the ones they just rotted, and the minutes come out wrong.
    • Marking too late. Setting the neighbour to 2 only when it is popped lets it be queued several times, which also breaks the count of fresh.

    Testing

    orangesRotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]) -> 4
orangesRotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]]) -> -1
orangesRotting([[0, 2]])                          -> 0
orangesRotting([[1]])                             -> -1
orangesRotting([[2, 1, 1, 1, 1]])                 -> 4
    Keep going with Python500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free