Rotting Oranges (LeetCode-994)

image from adobe spark

Today let’s try to look at the famous rotting oranges problem. Before proceeding to the problem it is highly recommended for you to know the basics of the data structure queue and the BFS traversal algorithm. To clear the pre-requisite concepts I would recommend you to go through the following links:

1. https://www.programiz.com/dsa/queue
2. https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/

Now that our basic concepts are cleared let us proceed to the problem statement and how to solve the problem!

Problem Statement

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.

Click the below link for seeing sample test cases

Rotting Oranges - LeetCode

Thinking approach

Let’s understand the approach we’ll be taking by seeing a test case.

Input: grid = [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

This is how to problem proceeds:

Time: 0s
2 1 1
1 1 0
0 1 1

We can see that the starting orange at (0,0) is rotten. So it will rot its two immediate neighbours at(1,0) and (0,1).

Time: 1s
2 2 1
2 1 0
0 1 1

Oranges at (0,1) and (1,0) will now spread it their immediate neighbours and the matrix then looks like-

Time: 2s
2 2 2
2 2 0
0 1 1

Now orange at (1,1) will start spreading it to its neighbour at (2,1). After which the matrix looks like-

Time: 3s
2 2 2
2 2 0
0 2 1

Now orange at (2,1) will spread it to the neighbouring orange at (2,2) and then the matrix will be-

Time: 4s
2 2 2
2 2 0
0 2 2

So it taskes 4s to rot all the oranges. We hence return 4.

You would have observed that the spreading of oranges rotting happens in a breadth-first manner, but there is a catch here. Spreading happens parallelly sometimes for more than one oranges and in that case, the time has to be increased by only 1 second. How do we deal with this?

This is where your knowledge in queues comes into action.

How??

We make a new structure which is given below:

In this structure, we store three variables namely,

1. time: This stores the timestamp when a particular orange comes into contact with another rotten orange and starts to rot.
2. x and y: store the respective coordinates of the particular orange.

Now the next step is to traverse the 2D matrix and store all the data (structure node) of the rotten oranges in a queue.

After this, we pop elements one by one from the queue. For each orange popped from the queue, its neighbours start rotting the next second. So we follow a BFS approach and add all its neighbour’s data in the queue. Always remember, while adding the neighbor’s data inside the queue, increase the timestamp by 1 and then push it in the queue as it starts rotting one second after coming into contact. Continue this process until the queue runs out of elements. Store the information (timestamp precisely) of the lost popped out node as that will contain the total time taken to rot all oranges.

Wait!!

The problem is not yet finished. There is one important feature that has to be done while popping and pushing elements in the queue. In the last paragraph whenever you pop an element from the queue, it means that the particular orange has become rotten, so change the value of that location to 2 indicating it's rotten. After the queue runs out check if there are any unrotten oranges left. If there are directly return -1, else return the timestamp of the last popped out node from the queue.

For a clear understanding try to check out the code given below as well!

Code:

Hope everyone understood the method and the intuition behind this amazing problem. Please do leave a clap if you liked the article. Thank you!!