994.Rotting_Oranges(Medium).md

994. Rotting Oranges (Medium)

Date and Time: Sep 24, 2024, 17:32 (EST)

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

Question:

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 0, 1, or 2.

Walk-through:

1. Loop over the grid to store total for total oranges we have, rotten and deque to store the [r, c] of the current rotten oranges we know.

2. We run BFS on the current rotten oranges we found, and we check their four neighbors, and append the oranges to deque if grid[r][c] == 1 (means we have fresh orange to rot), so we just append the new entry to deque and mark this entry as rotten orange.

3. Since we run while loop based on deque and (total - rotten) > 0, so if we have rotten all the fresh oranges, we will stop the while loop and we return moves or -1 based on if rotten == total or not.

Python Solution:

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        # Find min mins that all fresh oranges will be rotten
        # 1. Find all the rotten oranges into deque[]
        # Run BFS from all the rotten oranges, we append their neighbors into a deque[], update times += 1
        
        # TC: O(m x n), SC: O(m x n)
        deque = collections.deque()
        rows, cols = len(grid), len(grid[0])
        fresh = 0
        times = 0
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 2:
                    deque.append([r, c])
                elif grid[r][c] == 1:
                    fresh += 1
        
        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        # Use fresh > 0 to prevent when we can't reach a fresh orange
        while deque and fresh > 0:
            for _ in range(len(deque)):
                row, col = deque.popleft()
                for dr, dc in directions:
                    r, c = dr + row, dc + col
                    # Set grid[r][c] to be rotten and fresh -= 1
                    if r in range(rows) and c in range(cols) and grid[r][c] == 1:
                        deque.append([r, c])
                        grid[r][c] = 2
                        fresh -= 1
            times += 1
        
        return times if fresh == 0 else -1

Time Complexity: $O(m * n)$, m, n are the dimensions of grid.
Space Complexity: $O(m * n)$

Java:

class Solution {
    public int orangesRotting(int[][] grid) {
        /* Use deque and fresh to keep track of rotten oranges pos, and # of fresh oranges we have
        Use time var, every time we check the rotten oranges four directions, save their pos into deque[]
        In the end, check if there is no more fresh oranges, that means we have no more oranges

        TC: O(m * n), SC: O(m * n)
        */
        Queue<int[]> deque = new ArrayDeque<>();
        int fresh = 0;
        int time = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        // Traverse grid and mark rotten oranges
        for (int r=0; r<rows; r++) {
            for (int c=0; c<cols; c++) {
                // Add rotten orange to deque
                if (grid[r][c] == 2) {
                    deque.add(new int[] {r, c});
                } else if (grid[r][c] == 1) {
                    fresh++;
                }
            }
        }
        // Check deque and fresh > 0
        int[][] directions = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        while (deque.size() != 0 && fresh > 0) {
            int length = deque.size();
            for (int i=0; i<length; i++) {
                int[] list = deque.poll();
                int r = list[0], c = list[1];
                for (int[] dir: directions) {
                    int row = r+dir[0], col = c+dir[1];
                    // change fresh orange to be rotten
                    if (row<rows && row>=0 && col<cols && col>=0 && grid[row][col] == 1) {
                        grid[row][col] = 2;
                        fresh--;
                        deque.add(new int[] {row, col});
                }
                }
            }
            time++;
        }
        return fresh > 0 ? -1 : time;
    }
}