@dsadaily

  • Home
  • Tags
  • About
  • TryMe

Rotting Oranges

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Problem Statement

LeetCode-994: 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.

Approach

As with other problems involving a matrix, we can use a BFS traversal to solve this problem. Also, presence of multiple rotten oranges at the start requires us to start the traversal from all the rotten oranges.

Additionally, we need to keep track of the graph levels to determine the number of minutes that have elapsed. We can maintain a special entry in the queue to indicate the end of a level.

  1. Start by adding all the rotten oranges to a queue and then traverse the matrix in a BFS manner.
  2. Add the level separator to the queue to indicate the end of a level.
  3. While the queue is not empty, pop the front element:
    1. If the element is a level separator:
      • Increment the number of minutes that have elapsed and
      • Add another level separator to the queue.
    2. Else, it must be a rotten orange, so check all the 4 directions for fresh oranges:
      • If we find a fresh orange, we can rot it and add it to the queue.
      • Decrement the number of fresh oranges in the matrix.
  4. Once the queue is empty, check if there are any fresh oranges left in the matrix. If there are, return -1, else return the number of minutes that have elapsed.

Implementation

Here is a Java implementation of the above approach:

private record Coordinates(int row, int col){}

public int orangesRotting(int[][] grid) {
    Queue<Coordinates> queue = new LinkedList<>();
    int freshOranges = 0;
    int rows = grid.length, cols = grid[0].length;

    // add the co-od for all the rotten oranges
    // to the queue
    for (int row = 0; row < rows; row++){
        for (int col = 0; col < cols; col++){
            if (grid[row][col] == 2){
                queue.offer(new Coordinates(row, col));
            }
            else if (grid[row][col] == 1){
                freshOranges++;
            }
        }
    }
    // add level separator to the queue
    queue.offer(new Coordinates(-1, -1));
    
    // BFS
    int minutesElapsed = -1;
    int[] directions = { 0, 1, 0, -1, 0};
    while (!queue.isEmpty()) {
        Coordinates cood = queue.poll();
        int row = cood.row();
        int col = cood.col();

        // row == -1 denotes the level seperator
        // which denotes the passing of a minute
        // also, add another level seperator to 
        // mark the boundary of new level's entries
        if (row == -1) {
            minutesElapsed++;
            if (!queue.isEmpty()){
                queue.offer(new Coordinates(-1, -1));
            }
        } else {
            // rotten orange
            // traverse its neighbours to identify fresh oranges
            // that can be spoiled
            for (int i=0; i < 4; i++) {
                int neighborRow = row + directions[i];
                int neighborCol = col + directions[i+1];
                
                if (neighborRow >= 0 && neighborRow < rows && 
                    neighborCol >= 0 && neighborCol < cols) {
                    if (grid[neighborRow][neighborCol] == 1) {
                        // mark spoiled
                        grid[neighborRow][neighborCol] = 2;
                        freshOranges--;
                        // update queue for next level's entry
                        queue.offer(new Coordinates(neighborRow, neighborCol));
                    }
                }
            }
        }
    }
    
    // return elapsed minutes if no fresh orange left
    return freshOranges == 0 ? minutesElapsed : -1;
}

Complexity Analysis

The time complexity for this approach is $O(m \times n)$ where $m$ and $n$ are the number of rows and columns in the matrix respectively.

The space complexity is also $O(m \times n)$ as we are using a queue to store the rotten oranges.

See Also

Be notified of new posts. Subscribe to the RSS feed.