Rotting Oranges

Problem

You are given an m x n grid where each cell can have one of three values: 0 (empty cell), 1 (fresh orange), or 2 (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 elapse until no cell has a fresh orange. If this is impossible, return -1.

Examples

The brute-force approach

Each minute, scan the entire grid and mark any fresh orange adjacent to a rotten one as newly rotten. Repeat until no changes happen. Count the minutes.

minutes = 0
while grid has fresh oranges:
    changed = False
    new_rotten = []
    for each cell (r,c) that is fresh:
        if any neighbor is rotten:
            new_rotten.append((r,c))
            changed = True
    for (r,c) in new_rotten:
        grid[r][c] = 2
    minutes += 1
    if not changed and grid has fresh: return -1
return minutes

O((m×n)²) — each minute does a full O(m×n) scan, and this can repeat O(m×n) times.

Spotting the pattern

This is a Matrix Traversal problem. The key question to ask yourself:

If multiple rotten oranges exist from the start, which minute does each fresh orange rot? Can you compute all minutes in a single BFS pass?

Answering that is where it clicks, and it's exactly what the guided walkthrough below builds with you: the pattern reasoning, a progressive hint ladder that never spoils the answer, a row-by-row dry run, the optimized solution, and an in-browser editor to run your code against real test cases.