994. Rotting Oranges

#bfs #graph

Problem

Rotting Oranges - LeetCodeLeetCode

Intuition

Time Complexity

Space Complexity

Solution

class Solution {
    public int orangesRotting(int[][] grid) {
        // m -> rows n -> cols
        // Time Complexity: O(m * n)
        // O(m * n) (for traversing and adding rotten oranges to queue and counting fresh oranges)
        // O(m * n) (for BFS traversal)
        // O(m * n) + O(m * n)  = 2 * O(m * n)  = O(m * n) 
        
        // Space Complexity: O(m * n), storing the cells in the queue

        // Check for edge cases
        if (grid == null || grid.length == 0) {
            return -1;
        }

        // Define the directions for traversing the grid
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        // Get the number of rows and columns in the grid
        int rows = grid.length;
        int cols = grid[0].length;

        // Create a queue to store the coordinates of rotten oranges
        Deque<int[]> queue = new ArrayDeque<>();
        int countFresh = 0; // Count of fresh oranges

        // Iterate through the grid to find rotten and fresh oranges
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 2) {
                    // Add the coordinates of rotten oranges to the queue
                    queue.offer(new int[]{i, j});
                } else if (grid[i][j] == 1) {
                    // Count the number of fresh oranges
                    countFresh++;
                }
            }
        }

        // If there are no fresh oranges, the grid is already fully rotten
        if (countFresh == 0) {
            return 0;
        }

        int count = 0; // Count of minutes to rot all oranges
        while (!queue.isEmpty()) {
            int size = queue.size();

            // Process all the oranges at the current minute
            for (int i = 0; i < size; i++) {
                int[] current = queue.poll();
                int parentX = current[0];
                int parentY = current[1];

                // Check all four directions to rot adjacent fresh oranges
                for (int[] dir : dirs) {
                    int x = parentX + dir[0];
                    int y = parentY + dir[1];

                    // Skip if the coordinates are out of bounds or the orange is already rotten or empty
                    if (x < 0 || x >= rows || y < 0 || y >= cols || grid[x][y] != 1) {
                        continue;
                    }

                    // Mark the fresh orange as rotten and add its coordinates to the queue
                    grid[x][y] = 2;
                    queue.offer(new int[]{x, y});
                    countFresh--;
                }
            }
            count++; // Increment the count of minutes
        }

        // If there are still fresh oranges remaining, it is not possible to rot all oranges
        // Otherwise, return the count of minutes minus 1 since the last round does not count
        return countFresh == 0 ? count - 1 : -1;
    }
}