Rotting Oranges — LeetCode 994 Python Solution
MediumBreadth-First SearchArrayMatrix
- Problem
- #994
- Pattern
- Matrix and Grid
- Reading time
- 5 min
- Source
- leetcode.com
The problem
You are given an m x n grid where each cell can have one of three values: 0 representing an empty cell, 1 representing a fresh orange, or 2 representing a rotten orange. Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Example
- Input
- grid = [[2,1,1],[1,1,0],[0,1,1]]
- Output
- 4
Python solution
Python
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
cnt = 0
q = deque()
for i, row in enumerate(grid):
for j, x in enumerate(row):
if x == 2:
q.append((i, j))
elif x == 1:
cnt += 1
ans = 0
dirs = (-1, 0, 1, 0, -1)
while q and cnt:
ans += 1
for _ in range(len(q)):
i, j = q.popleft()
for a, b in pairwise(dirs):
x, y = i + a, j + b
if 0 <= x < m and 0 <= y < n and grid[x][y] == 1:
grid[x][y] = 2
q.append((x, y))
cnt -= 1
if cnt == 0:
return ans
return -1 if cnt else 0Complexity
| Measure | Complexity |
|---|---|
| Time | O(m \times n) |
| Space | O(m \times n) auxiliary |
Pattern: Matrix and Grid
Treat a 2-D grid as a graph whose neighbours are the four adjacent cells. LeetCode 994. Rotting Oranges is filed here because LeetCode tags it Matrix, which is the vocabulary this hub collects.
The matrix and grid guide has the Python template for the pattern and the 216 LeetCode problems that use it.
Related problems
On study lists
This problem is on NeetCode 150, Grind 75 and LeetCode 75.
Frequently asked questions
- How hard is LeetCode 994. Rotting Oranges?
- LeetCode 994. Rotting Oranges is rated Medium on LeetCode.
- What is the time complexity of LeetCode 994. Rotting Oranges?
- The Python solution on this page runs in O(m \times n).
- What is the space complexity of LeetCode 994. Rotting Oranges?
- The Python solution on this page uses O(m \times n) auxiliary space.
- What topics does LeetCode 994. Rotting Oranges cover?
- LeetCode 994. Rotting Oranges is tagged Breadth-First Search, Array and Matrix on LeetCode.