LeetCode 994: Rotting Oranges Solution

Master LeetCode problem 994 (Rotting Oranges), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

994. Rotting Oranges

Medium

Array Breadth-First Search Matrix

Problem Explanation

Explanation

To solve this problem, we can use a breadth-first search (BFS) approach. We start by initializing a queue with the positions of all rotten oranges. Then, in each iteration, we process all adjacent fresh oranges to the current rotten oranges, making them rotten and adding them to the queue. We continue this process until the queue is empty or no more fresh oranges can be infected.

Algorithm:

Initialize a queue to store the positions of rotten oranges and a variable to store the number of minutes passed.
Iterate through the grid to find all rotten oranges and add their positions to the queue.
While the queue is not empty, do the following:
- Increase the number of minutes passed.
- Process all adjacent fresh oranges to the current rotten oranges, making them rotten and adding them to the queue.
Check if there are any remaining fresh oranges in the grid. If yes, return -1; otherwise, return the number of minutes passed.

Time Complexity: O(m * n) where m is the number of rows and n is the number of columns in the grid. Space Complexity: O(m * n) in the worst case when all cells are rotten oranges.

Solution Code

class Solution {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        
        Queue<int[]> queue = new LinkedList<>();
        int freshOranges = 0;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                } else if (grid[i][j] == 1) {
                    freshOranges++;
                }
            }
        }
        
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int minutes = 0;
        
        while (!queue.isEmpty() && freshOranges > 0) {
            int size = queue.size();
            
            for (int i = 0; i < size; i++) {
                int[] curr = queue.poll();
                
                for (int[] dir : directions) {
                    int newRow = curr[0] + dir[0];
                    int newCol = curr[1] + dir[1];
                    
                    if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols && grid[newRow][newCol] == 1) {
                        grid[newRow][newCol] = 2;
                        freshOranges--;
                        queue.offer(new int[]{newRow, newCol});
                    }
                }
            }
            
            minutes++;
        }
        
        return freshOranges == 0 ? minutes : -1;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 994 (Rotting Oranges)?

This page provides optimized solutions for LeetCode problem 994 (Rotting Oranges) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 994 (Rotting Oranges)?

The time complexity for LeetCode 994 (Rotting Oranges) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 994 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 994 in Java, C++, or Python.

Back to LeetCode Solutions