Rotten Oranges Problem in Java

Matrix traversal is a common problem arising in computational problem-solving with relevance to path finding, simulation and games. One of such problems discussed on the web is the Rotten Oranges Problem that simulates the spread of rot on a grid of oranges. This is a theoretical performance and practical implementation of the BFS as well as the application of the graph traversal algorithms.

Problem Statement

The problem can be defined as follows:

You are given a 2D grid where:

• 0 represents an empty cell.
• 1 represents a fresh orange.
• 2 represents a rotten orange.

On each minute, any rotten orange causes the fresh oranges neighbour to them to rot which include the one above it, below it, to its left and to its right.

Your objective is to find the minimum time at which all oranges are rotted. If any fresh orange lies out of reach, -1 should be returned.

Example:

• First, the orange in the top left corner is bad.
• In one minute, it spoils the fresh oranges which lie beside it.
• In 2 minutes, the spread begins and after 4 minutes all the oranges go rotten.

Approach

It is a solution based on Breadth-First Search (BFS), more often used in level-order traversal in a graph. There are three reasons which makes BFS useful here: The rotting spreads level by level, so does BFS visiting nodes in the graph.

Steps to Solve the Problem

Initialization: Traverse the grid to:

• Count all fresh oranges.
• Push all the positions of rotten oranges to a queue because these will be the points of beginnings of BFS.

Breadth-First Search:

• Cancel an orange, which is rotten and examine the four cells around it up, down, left and right.
• Otherwise, if an adjacent cell is fresh orange, change it to rotten one, plus rotten oranges counter, and add its position in the queue.

Time Tracking: Keep a count of the number of minutes in the course of the inventory of BFS traversal.

Completion Check:

• If there are no fresh oranges remaining cause BFS, then return the measured time taken.
• If some fresh oranges are left then return -1.

File Name: RottenOranges.java

Output:

 
Minimum time to rot all oranges: 4   

Complexity Analysis

Time Complexity

The procedure of BFS traversal implies that each cell is processed within the algorithm at most one time.

The time complexity of this solution is O(N×M) because it brings out the worst in each of these algorithms.

Space Complexity

Space is needed for the queue, and it may contain at most O(N×M) elements in the worst circumstance.

Conclusion

The Rotten Oranges Problem is a great tool to show representative applications of BFS including the propagation of contamination such as infections, the modeling of wildfires and various diffusion sets.

Rotating adjacent cells and tracking time in this way can also guarantee efficiency and accuracy at the same time. In Java, doing this solidifies basic ideas of graphs and using a queue to process the graph.

This problem also includes tricky cases, for example, if there are no fresh oranges or if some fresh oranges are unreachable. This is so because it has tangible uses apart from being highly charged on algorithms where members are obsessed with solving it.