Leetcode Problem 994- rotting oranges solution won't work :(

Question

So I've come across this problem while trying to enhance my skills. I watched the Neetcode solution video to it 2 days ago, where he goes over a detailed solution, and I decided to tackle it myself today since I didn't have his code fresh on my mind, but I still had the intuition and hence, I thought I could maybe be able to solve it on my own, but oh how I was wrong..... After SEVERAL errors thrown that I solved, I got stuck with this error RuntimeError: deque mutated during iteration which I don't understand. I went through the logic and the solution makes sense to me & I don't understand why it won't budge. Watching a solution video and not being able to come to one myself due to some dumb runtime error makes me feel extremely inadequate about my skills and essential makes me feel like garbage. I put a lot of effort into making this solution, yet it just won't damn run. If anyone could help me out, I would GREATLY appreciate that. Im very hopeless right now.

from collections import deque

def orangesRotting(grid):
    time = 0
    row, col = len(grid), len(grid[0])
    rotten = deque()
    fresh = 0
    isrotting = []
    for r in range(row):
        for c in range(col):
            if grid[r][c] == 1:
                fresh += 1
            if grid[r][c] == 2:
                rotten.append((r,c))
    def helper(r, c, fresh):
        if r < 0 or r == row or c < 0 or c == col or grid[r][c] != 1:
            return
        grid[r][c] = 2
        fresh -= 1
        isrotting.append((r,c))
    while rotten or fresh > 0:
        for (ri, ci) in rotten:
            helper(ri, ci + 1, fresh)
            helper(ri, ci - 1, fresh)
            helper(ri + 1, ci, fresh)
            helper(ri - 1, ci, fresh)
            rotten.pop()
            if (ri, ci) in isrotting:
                isrotting.remove((ri, ci))
        for (rrtn, crtn) in isrotting:
            rotten.append((rrtn, crtn))
        time += 1
    if not rotten and fresh > 0:
        time = -1
    return time
   
grid = [[2,1,1],[1,1,0],[0,1,1]]
print(orangesRotting(grid))

DarrylG · Answer

One refactoring keep as much as possible of posted code.

Code

from collections import deque

def orangesRotting(grid):
    # Placed helper function at the top so as not to intermix with code
    def helper(r, c, steps):
        # Update if inside grid and grid value at r, c is fresh (=1)
        nonlocal fresh  # make nonlocal so we can update fresh in orangesRotting
        
        if 0 <= r < row and 0 <= c < col and grid[r][c] == 1:
            grid[r][c] = 2
            fresh -= 1
            rotten.append((r, c, steps))

    # Setup
    rotten = deque()
    fresh = 0
    row, col = len(grid), len(grid[0])
    for r in range(row):
        for c in range(col):
            if grid[r][c] == 1:
                fresh += 1                # adding all fresh cells   
            elif grid[r][c] == 2:
                rotten.append((r, c, 0))  # tuple: row, column, step
    
    # Find the number of steps using breadth-first search
    while rotten:                         # loop until we are out of rotten to branch from
        ri, ci, steps = rotten.popleft()  # pop left provides breadth-first search
                                          # to step
        helper(ri, ci + 1, steps + 1)     # increment steps and make row, column rotten
        helper(ri, ci - 1, steps + 1)
        helper(ri + 1, ci, steps + 1)
        helper(ri - 1, ci, steps + 1)
   
    return steps if not fresh else -1      # return steps if fresh == 0 else -1

Tests

for grid in [[[2,1,1],[1,1,0],[0,1,1]],
             [[2,1,1],[0,1,1],[1,0,1]]]:
    print(f"{grid} : {orangesRotting(grid)}")

Output

[[2, 1, 1], [1, 1, 0], [0, 1, 1]] : 4
[[2, 1, 1], [0, 1, 1], [1, 0, 1]] : -1

Leetcode Problem 994- rotting oranges solution won't work :(

1 Answers