Leetcode #994 Rotting Oranges
In today’s blog, we will talk about another back it again at the algorithm question. This time is a little bit harder. I usually solve Breadth-First-Search (BFS) in a tree problem. Never in my life have I solved it with a non-tree data structure. For that reason, this problem is a good example to test the water. It is a popular interview question among big FANGG companies, especially Amazon (if you know). So let’s not talk more about it and dive deeper into the problem.
Here is the problem:
Why do we use BFS and not DFS?
Before jumping into the code, we should think about what kind of data structure/ algorithm we should utilize with this type of problem. Well, I already spoiled that we use BFS to solve this problem, but why not Depth-First-Search (DFS)? The answer is that BFS and DFS both could work for this problem, but BFS would be a better fit. As we know, the BFS Strategy prioritizes the breadth over depth (wider before it goes deeper). On the other hand, the DFS strategy prioritizes depth over breadth. These strategies tell us, with DFS, we usually process one single node at each step, while in BFS, we could process multiple clusters of nodes. Imagine several rotten oranges are distributed in different corners in the grid; We know that rotten oranges will contaminate their neighbors first before the contamination propagates to other fresh oranges. With BFS, at each step (iteration), we can figure out all the oranges that would be contaminated in the next round (minute). However, with DFS, we only explore one direction in-depth before trying out other directions. If you are not familiar with BFS/DFS, you can check this article(https://medium.com/swlh/bfs-vs-dfs-9b644c6c713c).
Intuition
We want to check the neighbors for the rotten oranges. We can think of checking one single unit of the top, down, left, and right from each rotten orange coordination until it reaches the farthest fresh oranges. With the BFS (queue) idea, we can find all the fresh oranges going to get contaminated.
Algorithm
First, we calculate the total fresh oranges in the M x N grid and find all the rotten oranges coordinate. If there are no fresh oranges, we can return 0. Otherwise, we have to coordinate checking the rotten oranges neighbors (West, East, North, South of the rotten oranges). Now we start traversing the 2d array matrix, with these two conditions, as long as there are still fresh oranges left and still rotten oranges left to be spread. We traverse the 2d matrix array based on the rotten oranges. One edge case that we need to know is that if there is a fresh orange that is never rotten, we need to return -1. I explained my code down below with some comments for more details. (disclaimer: It took me almost the whole day, and I was not able to solve it, therefore, I checked the solution and learned from it, or else is not productive at all. There is no shame in checking the solution after 1–2 hours stuck in the same problem, as long as you understand and learn the intuition from it. )
Time & Space Complexity
The time complexity is O(N), where N is the size of the grid. First, we scan the grid to get the queue’s initial values, which would take O(N) time. With the BFS process, the worst case would run through all the grid cells once and only once, O(N). The overall time complexity would be O(N) +O(N)=O(N)
The space complexity is O(N), where N is the size of the grid. In the worst case, the grid is filled with rotten oranges. As a result, the queue would be initialized with all the cells in the grid.
Just a heads up, usually BFS in a tree, the space complexity lies in the process rather than the initialization; the queue would hold no more than two levels of tree nodes. The space complexity traversal in the tree would depend on the width of the input tree.
Thanks for reading my article. If you enjoyed what you read, consider connecting. Thanks again, and I hope you have a great wonderful day.