MediumNeetCode150ArrayBreadth-First SearchMatrix

Rotting Oranges

Return minutes until no fresh orange remains.

Examples

Input
grid = [[2,1,1],[1,1,0],[0,1,1]]
Output
4

Minutes until all rot.

Constraints

  • •m,n == grid.length
  • •0 <= grid[i][j] <= 2

Approaches

Multi-source BFS.

CodeT: O(m*n) | S: O(m*n) queue
from collections import deque
def orangesRotting(grid):
    r,c=len(grid),len(grid[0]); q=deque(); fr=0
    for i in range(r):
        for j in range(c):
            if grid[i][j]==2: q.append((i,j))
            elif grid[i][j]==1: fr+=1
    if fr==0: return 0
    mn=0
    while q:
        for _ in range(len(q)):
            x,y=q.popleft()
            for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
                nx,ny=x+dx,y+dy
                if 0<=nx<r and 0<=ny<c and grid[nx][ny]==1:
                    grid[nx][ny]=2; fr-=1; q.append((nx,ny))
        mn+=1
    return mn-1 if fr==0 else -1

Same approach.

CodeT: O(m*n) | S: O(m*n)

All rotten oranges as sources.

CodeT: O(m*n) | S: O(m*n)

Complexity Comparison

BFS
T: O(m*n)S: O(m*n) queue

Multi-source BFS.

BFS Optimized
T: O(m*n)S: O(m*n)

Same approach.

Multi-source BFS
T: O(m*n)S: O(m*n)

All rotten oranges as sources.

Common Mistakes

Not handling no fresh oranges

Wrong minute count

Not checking remaining fresh

Try It Yourself

Copy the optimal solution and run it in our compiler.

▶Open in Compiler
← All Problems