A quick ride through my thought process while solving problem- “Rotting Oranges”

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

If you are practicing data structures and algorithm problems, you must be familiar with the problem “Rotting Oranges” mainly implemented using BFS. Honestly speaking, It took me three months and multiple incorrect attempts to get me right solution. I gave my first attempt on 2nd April, got a run time error ,even posted the issue on Leetcode discuss but to no help. Beside it being a very important problem for interviews, I was kind of emotionally attached to the problem because a similar kind was asked to me in my google interview which I failed. So, when I was finally able to solve it correctly on 2nd July(Exactly 3 months!!!), i was pretty much excited to share my journey of these 3 months which included four wrong submissions every time giving me a new idea to improve further . So, here is the problem statement.

In a given grid, each cell can have one of three values:

• the value 0 representing an empty cell;
• the value 1 representing a fresh orange;
• the value 2 representing a rotten orange.

Every minute, any fresh orange that is adjacent (4-directionally) 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 instead.

Example 1:

Okay! So, its pretty much clear that its a graph problem.

Confusion 1: DFS or BFS??

Now, as we see we are concerned with all the neighbors of a rotten orange.So, we have to look for all the neighbors of a node first and then move to their neighbors making it a BFS problem.

Okay! So, now lets break the problem into small cases.

Case 1: If there is no fresh orange in the given grid.Then simply return 0.

Case 2: If first one is not true and there are fresh oranges in the grid but there are no rotten oranges return -1.

Point of potential mistake: If you check condition 2 first and simply return -1 if there are no rotten oranges without checking if fresh oranges are also present or not, then you are simply giving yourself just one more WA.

First Intuition: What do we need to insert into queue? Which information will be useful to us? Was it value of grid(i.e 0/1/2)? But, then how can I trace the neighbor of rotten oranges? So, plain answer was indices!!

Believe me or not, but I was stupid enough to insert a vector inside my queue which contained 3 integers- indices and the value of grid at those index. So, Lets give a look how i traveled from this stupid idea to a fully correct algorithm.

Second Intuition: How to keep the record of rotten oranges which are already inserted into the queue once? Because if we dont, then we might end up in an infinite loop. Like I would have to keep a visited array that will keep the record of rotten oranges which are already processed. For me, it was a very tedious and space consuming process. So, I decided to keep it simple. And change the value of every processed rotten orange to 0. And after that we don’t need to worry about them.

And by processed I mean when I have inserted a rotten orange into the queue.

Now,first let me take you through series of mistakes that i did which resulted in failed submissions and how I dealt with them to reach a perfect(303/303) solution, then we can discuss the final and full algorithm.

Mistake 1: Failed at test case Input= [[1,2]] , Output=-1, Expected Output=1 after passing 105 test cases.

So, I was basically inserting only (0,0) into the queue before I started the while loop of BFS. I realized this was a huge mistake after a long time. Then what do we have to actually insert? Keep following!!!!

Mistake 2: Inserted first element which was rotten. For this I used two ‘for loops’ looked for first rotten orange and inserted its index into queue then ‘break’ and came out of the loops. Gave a little pat on my back only to see it fail at 121st test case. Input=[[2,0,1,2,1,2]], Output=-1, Expected=1.

I realized it to be a mistake as I could see my other rotten oranges (disconnected from the first one) are never ever getting into the queue only .

So, I corrected this by inserting the index of all the rotten oranges before entering the BFS loop. Hooray!! A correct attempt.

Mistake 3: I was incrementing the time every time I removed an element from the queue. Honestly speaking, I didn’t know why!!! So, it gave me wrong answers.

Mistake 4: I tried to correct it by incrementing it only when I have changed a fresh orange into rotten. But yet I got wrong answers for cases like [[1,2,1,1,2,1,1]] O/P: 3, Expected: 2.

And this point was breakthrough moment of my journey because after correcting this mistake, I was ready to rock with a fully correct solution which was faster than 94% submissions.

I realized that (and the words of Google interviewer came clear in my mind) all the bombs will explode at the same time. What I was doing is that handling one rotten orange at a time and incrementing time for every rotten orange. But no!!! I had to deal all the present rotten orange in one go. Hence I used a variable levelsize=q.size() and after I am done with a level, I increment the time once.

So, lets take a quick walk through final algorithm step by step.

1. Handle the case 1 and 2 mentioned above.
2. Insert the index of all the rotten oranges present in the given grid into the queue.
3. Loop while queue is not empty.
4. Run inner loop for levelsize=q.size(), basically processing all the rotten oranges present at one time in one go.
5. Pop out the front element from queue(it will always be rotten!), look for it neighbors.
6. Check if its a valid neighbor i.e. row and col are within the boundary and are non zero( If its zero we don’t need to do anything with them).
7. So, if its a valid one, Push them to queue and make their value zero( because we have visited them and after pushing into queue, we dont need to do anything else with them).
8. Now, increment time when one level is completed.
9. Repeat the process until queue becomes empty.
10. Look for final condition i.e. if any fresh orange is still present in the grid return -1 else return (time-1);
11. Now, why (time-1)? Because, we were incrementing time for the last batch( level) also, which do not have any unprocessed neighbors so they dont contribute anything. They just have to be removed from the queue. So, decrementing time by 1.

I hope you understood the algorithm.

Here is my final solution!!!

Thank You for your patience guys!!!!!