LeetCode 994. Rotting Oranges

Description

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

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.

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] is 01, or 2.

Explanation

We can use bread-first search to find out the rotten oranges at each minute.

Python Solution

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        minutes = -1
        queue = []
        
        all_empty = True
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 2:
                    queue.append((i, j))
                    all_empty = False
                elif grid[i][j] == 1:
                    all_empty = False
                    
                    
        if all_empty:
            return 0
        
        while queue:            
            minutes += 1
            
            size = len(queue)           
            for _ in range(size):
                rotten = queue.pop(0)
                
                i = rotten[0]
                j = rotten[1]
                
                grid[i][j] = 2
                
                if i - 1 >= 0:
                    left = (i - 1, j)                    
                    if grid[left[0]][left[1]] == 1 and left not in queue:
                        queue.append(left)
                    
                if i + 1 <= len(grid) - 1:
                    right = (i + 1, j)
                    if grid[right[0]][right[1]] == 1 and right not in queue:
                        queue.append(right)
                        
                if j - 1 >= 0:
                    up = (i, j - 1)
                    if grid[up[0]][up[1]] == 1 and up not in queue:
                        queue.append(up)
                
                if j + 1 <= len(grid[0]) - 1:
                    down = (i, j + 1)
                    if grid[down[0]][down[1]] == 1 and down not in queue:
                        queue.append(down)                
        


        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    print (i, j)
                    
                    return -1
                                    
        
        return minutes
        
  • Time Complexity: O(N^2).
  • Space Complexity: O(N^2).

Leave a Reply

Your email address will not be published.