994. Rotting Oranges

Description

The problem is to determine the minimum amount of time required for all oranges in a grid to rot. The grid contains three types of cells:

• 0 representing an empty cell,
• 1 representing a fresh orange, and
• 2 representing a rotten orange.

Each minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten. The goal is to return the minimum number of minutes required for all fresh oranges to rot. If it's impossible for all the fresh oranges to rot, return -1.

Intuition

The problem can be solved using a Breadth-First Search (BFS) approach. BFS is suitable here because we need to explore all nodes (fresh oranges) layer by layer from the initially rotten oranges. This ensures that we track the time taken for the rotting process level by level.

Approach

1. Initialize a Queue and Count Fresh Oranges: - Traverse the grid to count the number of fresh oranges. - At the same time, add the position of all initially rotten oranges to a queue.
2. Breadth-First Search (BFS): - Use the queue to process each rotten orange. - For each rotten orange, rot all adjacent fresh oranges and add them to the queue. - Track the time taken for each layer of BFS.
3. Check Remaining Fresh Oranges: - After the BFS completes, check if there are any fresh oranges left. If so, return -1 as it's impossible to rot all oranges. Otherwise, return the time taken.

Complexity

Time Complexity:

• The time complexity is O(m * n), where m is the number of rows and n is the number of columns in the grid. This is because each cell is processed at most once.

Space Complexity:

• The space complexity is also O(m * n) because in the worst case, all cells could be added to the queue.

Code

C++

class Solution {
public:
    int orangesRotting(vector>& grid) {
        int time = 0;
        queue> q;
        int m = grid.size();
        int n = grid[0].size();

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    q.push({i, j});
                }
            }
        }
        vector> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        while (!q.empty()) {
            int size = q.size();
            time++;
            for (int k = 0; k < size; k++) {
                auto [x, y] = q.front();
                q.pop();
                for (auto [i, j] : directions) {
                    int newX = x + i;
                    int newY = y + j;
                    if (newX < 0 || newX >= m || newY < 0 || newY >= n || grid[newX][newY] == 0 || grid[newX][newY] == 2) {
                        continue;
                    }
                    if (grid[newX][newY] == 1) {
                        grid[newX][newY] = 2;
                        q.push({newX, newY});
                    }
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    return -1;
                }
            }
        }
        return time == 0 ? 0 : time - 1;
    }
};

Python

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        queue = deque()
        fresh_oranges = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    queue.append((i, j))
                elif grid[i][j] == 1:
                    fresh_oranges += 1
        if fresh_oranges == 0:
            return 0
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        time = 0
        
        while queue:
            time += 1
            for _ in range(len(queue)):
                x, y = queue.popleft()
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == 1:
                        grid[nx][ny] = 2
                        queue.append((nx, ny))
                        fresh_oranges -= 1
            if fresh_oranges == 0:
                return time
        return -1

Java

class Solution {
    public int orangesRotting(int[][] grid) {
        int time = 0;
        Queue queue = new LinkedList<>();
        int m = grid.length;
        int n = grid[0].length;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    queue.add(new int[]{i, j});
                }
            }
        }

        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

        while (!queue.isEmpty()) {
            int size = queue.size();
            boolean foundFresh = false;

            for (int k = 0; k < size; k++) {
                int[] cell = queue.poll();
                int x = cell[0], y = cell[1];
                
                for (int[] dir : directions) {
                    int newX = x + dir[0];
                    int newY = y + dir[1];
                    if (newX < 0 || newX >= m || newY < 0 || newY >= n || grid[newX][newY] == 0 || grid[newX][newY] == 2) {
                        continue;
                    }
                    if (grid[newX][newY] == 1) {
                        grid[newX][newY] = 2;
                        queue.add(new int[]{newX, newY});
                        foundFresh = true;
                    }
                }
            }
            if (foundFresh) {
                time++;
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    return -1;
                }
            }
        }

        return time;
    }
}

JavaScript

var orangesRotting = function(grid) {
    let time = 0
    const queue = []
    const m = grid.length
    const n = grid[0].length
    for(let i = 0; i < m; i++){
        for(let j = 0; j < n; j++){
            if(grid[i][j] === 2){
                queue.push([i,j])
            }
        }
    }
    while(queue.length > 0){
        const size = queue.length
        time += 1
        for(let k = 0; k < size; k++){
            const [x, y] = queue.shift()
            for(let [i,j] of [[0,1],[0,-1],[1,0],[-1,0]]){
                if(x+i < 0 || x+i >= m || y+j < 0 || y+j >= n || grid[x+i][y+j] === 0 || grid[x+i][y+j] === 2)continue
                if(grid[x+i][y+j] === 1){
                    grid[x+i][y+j] = 2
                    queue.push([x+i,y+j])
                }
            }
        }
    }
    console.log(grid)
    for(let i = 0; i < m; i++){
        for(let j = 0; j < n; j++){
            if(grid[i][j] === 1)return -1
        }
    }
    return time === 0 ? 0 : time-1
};