[Leetcode]994. Rotting Oranges

📄 Description

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.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Example 1:

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

Example 2:

Input: grid = [[2,1,1],[0,1,1],[1,0,1]] Output: -1 Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3:

Input: grid = [[0,2]] Output: 0 Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

💻 My Submission

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        R,C =len(grid), len(grid[0])
        rotten=[]
        # find rotten oranges
        for i in range(R):
            for j in range(C):
                if grid[i][j]==2: 
                    rotten.append((i,j))

        minute=0
        while rotten:
            adj_q=[]
            while rotten:
                position=rotten.pop(0)
                r,c=position[0],position[1]
                # check if its neighbor are fresh
                if r+1<R and grid[r+1][c]==1: 
                    grid[r+1][c]=2
                    adj_q.append((r+1,c))
                if r-1>=0 and grid[r-1][c]==1: 
                    grid[r-1][c]=2
                    adj_q.append((r-1,c))
                if c+1<C and grid[r][c+1]==1: 
                    grid[r][c+1]=2
                    adj_q.append((r,c+1))
                if c-1>=0 and grid[r][c-1]==1: 
                    grid[r][c-1]=2
                    adj_q.append((r,c-1))
            # if all the adjacent cell got rotten, 1 minute pass
            if adj_q:
                minute+=1
                rotten.extend(adj_q)
        
        # If there is fresh orange left then return -1
        for i in range(R):
            for j in range(C):
                if grid[i][j]==1:
                    return -1

        return minute

💊 Better Solution

	def orangesRotting(self, grid):
		''' Fresh and Rotten Hash Set to track fresh and rotten oranges'''
		fresh = set()
		rotten = set()

		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					fresh.add(str(i) + str(j))
				elif grid[i][j] == 2:
					rotten.add(str(i) + str(j))
				
		minutes = 0
		directions = [[0,1], [1,0], [-1,0], [0,-1]]

		"""while fresh oranges exist"""
		while fresh:
			infected = set()
			'''for every rotten orange, check if its neighbors are fresh'''
			for orange in rotten:
				i = int(orange[0])
				j = int(orange[1])

				for direction in directions:
					nextI = i + direction[0]
					nextJ = j + direction[1]

					'''if fresh, remove from fresh and add it to infected'''
					if (str(nextI) + str(nextJ)) in fresh:
						fresh.remove(str(nextI)+str(nextJ))
						infected.add(str(nextI) + str(nextJ))

			if not infected:
				return -1
			rotten = infected
			minutes += 1


		return minutes

References
https://leetcode.com/problems/rotting-oranges/
https://leetcode.com/problems/rotting-oranges/discuss/569638/Efficient-Python-Solution-O(N)-Time-Complexity