Rotten Oranges

XXX. Rotting Oranges

Breadth-First Search

Simulation

Problem Statement:

You are given an m x n grid where each cell can have one of three values:

• 0: Empty cell
• 1: Fresh orange
• 2: Rotten orange

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes needed to rot all the oranges. If it is impossible, return -1.

Approach:

1. Use a **Breadth-First Search (BFS)** approach to process the grid layer by layer.
2. Initialize a queue to keep track of rotten oranges and count the total number of fresh oranges.
3. While there are still oranges in the queue, process all the rotten oranges in the current layer (minute).
4. For each rotten orange, mark its adjacent fresh oranges as rotten and add them to the queue.
5. Increment the time counter for each layer processed.
6. If all fresh oranges are rotted, return the time counter. Otherwise, return -1 if there are still fresh oranges left.

Algorithm Intuition:

This problem is a classic **layer-by-layer BFS simulation**.

• Think of the grid as a graph where each cell is a node, and edges connect neighboring cells.
• The initial set of rotten oranges acts as the starting layer. From there, we "spread" the rot to adjacent fresh oranges in successive layers (minutes).
• The BFS ensures that we process all oranges at the same "depth" (minute) before moving to the next layer, giving us the exact time it takes to rot all oranges.
• If there are still fresh oranges left after processing all layers, it means they are isolated and cannot be rotted.

Complexity:

Time Complexity: O(m * n), where m and n are the grid dimensions. Each cell is processed at most once.
Space Complexity: O(m * n), for the queue used in the BFS.

Java Implementation:

// LAYER BY LAYER BFS SIMILAR TO THE size = q.size() METHOD!!!!!
public int orangesRotting(int[][] grid) {
    Queue q = new LinkedList<>();
    int minutes = 0;
    int freshOranges = 0;

    // Initialize the queue with all rotten oranges and count fresh oranges
    for (int i = 0; i < grid.length; i++) {
        for (int j = 0; j < grid[0].length; j++) {
            if (grid[i][j] == 2) 
                q.offer(new Orange(i, j)); // Add rotten orange to queue
            else if (grid[i][j] == 1) 
                freshOranges++; // Count fresh oranges
        }
    }

    int[][] dirs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 4 possible directions

    // Perform BFS to rot fresh oranges
    while (!q.isEmpty()) {
        if (freshOranges == 0) return minutes; // All oranges are rotted
        int size = q.size(); // Number of rotten oranges in the current layer
        minutes++;
        for (int i = 0; i < size; i++) {
            Orange currRottenOrange = q.poll();
            for (int[] dir : dirs) {
                int x = currRottenOrange.x + dir[0];
                int y = currRottenOrange.y + dir[1];

                // Add fresh orange neighbors that now became rotten
                if (x >= 0 && y >= 0 && x < grid.length && y < grid[0].length && grid[x][y] == 1) {
                    q.add(new Orange(x, y));
                    grid[x][y] = 2; // Mark as rotten
                    freshOranges--;
                }
            }
        }
    }

    // If fresh oranges remain, return -1
    return freshOranges == 0 ? minutes : -1;
}

// Helper class to represent an orange's position
class Orange {
    int x, y;
    public Orange(int x, int y) {
        this.x = x;
        this.y = y;
    }
}