FilesExpand file tree

 main

/

Rotting_Oranges.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

53 lines (46 loc) · 1.65 KB

 main

/

Rotting_Oranges.py

Copy path

Top

File metadata and controls

• Code
• Blame

53 lines (46 loc) · 1.65 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

"""

https://leetcode.com/problems/rotting-oranges/

Comments included with the code.

The idea is to go a BFS level order traversal from each rotting orange, then

add 1 to minutes elapsed after each level. Keep a count of how many pure oranges

remained at each point, and when they reach zero, return minutes elapsed.

"""

class Solution(object):

def orangesRotting(self, grid):

"""

:type grid: List[List[int]]

:rtype: int

"""

dirs = [(0,1),(1,0), (-1,0), (0,-1)]

q = []

rows, cols = len(grid), len(grid[0])

pure_count =0

# we will do a bfs from a rotten orange

# first, get the number of pure oranges

# then add all the rotten oranges in a queue

for i in range(rows):

for j in range(cols):

if grid[i][j]==2:

q.append((i,j))

if grid[i][j]==1:

pure_count+=1

if pure_count==0:

return 0

if not q:

return -1

# making minutes start from -1, for convenience,

# as at the next (0th) minute, we will just add

# the neighbors to the queue, not rot them until the minute after that.

minutes=-1

while q:

next_level = []

for i, j in q:

for dx, dy in dirs:

x,y = i+dx, j+dy

if x>=0 and y>=0 and x<rows and y<cols and grid[x][y]==1:

grid[x][y] = 2

pure_count-=1

next_level.append((x,y))

q = next_level

minutes+=1

return minutes if pure_count==0 else -1