TL;DR:
# ▼▼▼ START: Some_documentation ▼▼▼
# ▲▲▲ END: Some_documentation ▲▲▲
# Example:
# solution to https://leetcode.com/problems/rotting-oranges
from collections import deque
from typing import List
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
q = deque()
freshCnt = 0
m, n = len(grid), len(grid[0])
# Initial pass to find fresh/rotten oranges and check for isolated cells
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
freshCnt += 1
# ▼▼▼ START: NEW LOGIC FOR EARLY EXIT ▼▼▼
has_non_empty_neighbor = False
# Check all 4 potential neighbors
for di, dj in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
ni, nj = i + di, j + dj
# First, ensure the neighbor is within the grid bounds
if 0 <= ni < m and 0 <= nj < n:
# If we find any neighbor that isn't an empty cell,
# this orange is NOT isolated.
if grid[ni][nj] != 0:
has_non_empty_neighbor = True
break # No need to check other neighbors
# If after checking all valid neighbors, none were found,
# this orange is completely surrounded by empty cells.
if not has_non_empty_neighbor:
return -1 # Early exit
# ▲▲▲ END: NEW LOGIC FOR EARLY EXIT ▲▲▲
elif grid[i][j] == 2:
q.append((i, j))
time = 0
# This BFS part of your logic is correct
while q and freshCnt > 0:
for _ in range(len(q)):
i, j = q.popleft()
for ni, nj in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1):
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
q.append((ni, nj))
grid[ni][nj] = 2
freshCnt -= 1
time += 1
return time if freshCnt == 0 else -1
