 # Rotting Oranges

Leetcode: https://leetcode.com/problems/rotting-oranges/

At each time interval, the rotten oranges are going to rot the adjacent oranges. Minimum time to rot all the oranges.

## Solution Concepts

### First Concept

What I liked about this problem was that I had to use a queue to have a list of all the rotten orange coordinates. It is easy to keep them in a queue, but at each step, I need to add adjacent oranges to the queue as well. So how will I keep count of the time?

Example:

``````while(!q.isEmpty()) {
time++;
int elem = q.remove();
}``````

With this approach, I will incorrectly handle the time.

To solve it

``````while(!q.isEmpty()) {
time++;
int queueSize = q.size();
for(int i=0;i<queueSize;i++) {
...
...
}
}``````

With this approach, I need not run two queues or bother with size, it is awesome.

Second Concept To store a list of coordinates in queue

``````Queue<int []> q = new LinkedList<>();

This is amazing, I need now create a class now to store the coordinates. I am creating a queue of array elements and I will add coordinates to the queue in the form of an array. Very smart!!

Third concept I need to go in the following directions, up, down, left, right

``int directions[][] = {{0,1},{0,-1},{-1,0},{1,0}};``

now get a coordinate and loop through the directions and create new direction by adding the existing coordinate with the direction `x` and `y`

``````for(int dir[]: dirs) {
int newX = x + dir;
int newY = x + dir;

// validate newX and newY
}``````

Brilliant!!

#algorithm #data structures