Q82: Rotting Oranges. - DSA Patterns (Multi-Lang)

In Simple Words: Multi-source BFS. Enqueue all initially rotten oranges 2, count fresh oranges 1. At each minute, infect adjacent fresh oranges. If fresh oranges remain at end, return -1.

Time: $O(M \cdot N)$ | Space: $O(M \cdot N)$

Multi-Language SolutionsPython 3 • JavaScript • TypeScript • Java • C++

Switch tabs or choose All

from collections import deque

def orangesRotting(grid: list[list[int]]) -> int:
    q = deque()
    fresh = 0
    rows, cols = len(grid), len(grid[0])
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2: q.append((r, c))
            elif grid[r][c] == 1: fresh += 1
    if fresh == 0: return 0
    time = 0
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    while q and fresh > 0:
        for _ in range(len(q)):
            r, c = q.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    q.append((nr, nc))
        time += 1
    return time if fresh == 0 else -1