Decoding the BFS questions (Part 1a)

A step by step, well guided and curated list of Breath First Search questions, that you won’t find anywhere on the internet!

So how hard are these maze and matrix based questions envolving queues and binary matrices and visited arrays for you?

Well they were very hard to me! For a long time!

I have grinded down questions from LeetCode, understood the patterns, learnt a lot from the discussion panel, the LeetCode community is the best thing for your interview prep, hands down!

So I will be posting here section wise segregated questions from the most famous and quite difficult looking questions when seen for the first time.

I will be starting with BFS and the series will be broken down into 4 sub sections:

1. The grid based questions (Will be discussed in Part 1)
2. The flood fill based questions
3. The Topological sort related stuff
4. Some more miscellaneous content related to BFS

So lets get started with the grid based questions. Code will be in python, but it doesn’t actually matter if you understand the algorithm!

For this post we begin with the first question now, there are three questions of this grid based category, all work on similar lines. Lets get started!

ROTTING ORANGES

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

Every minute a rotten orange, degrades the fresh ones that are right next to it! Here in the example below only [0,0] is rotten to begin with.

1. [0,0] guy degrades the guy on its right and the guy below it( note that degradation works only in up, right, down, left directions) So in the 1st minute, 3 oranges are down!
2. Now [0,1] and [1,0] are also rotten, they will eat up who ever is around them! They cant eat out of bounds obviously and the empty spaces wont benefit them either. All they are hunting for is: Valid places with fresh oranges!
3. So at the end of 2nd minute 5 oranges are down. I hope you got the idea now!
4. We need to keep going until we eat up all the fresh oranges in our little yard! Pretty evil!

The rotting oranges

Initial takes: The rotten ones should be my prime concern, I also need a running minutes counter. The empty cells are a paradise to me I need not think much about them. What about the fresh ones? I need to kill ’em all!

What will I need? A variable to store how many fresh oranges I have at every moment! A variable for keeping the minutes counter.

Also I need to perform a BFS, but wait a minute, why BFS?

Because I need to look around each guy! All four directions! Because I need to go layer by layer. I need to pickup a cell and see all the guys right next to it! In almost all such cases the way to is BFS. You don’t need to worry if you do not agree right now, 10 more questions down the line ( I have them planned out) and you will start noticing the patterns!

Alright now so we need BFS. You hear the word BFS and the first thing that should strike your mind is: QUEUE DATA STRUCTURE!

Why queue? Because we need to maintain an order. An order in which we are exploring the elements. First in first out! The rotten orange I saw first needs to be dealt with first, the oranges that it has turned to rotten, should be processed later. That’s why queue!

The algorithm:

1. Put all initial rotten cells’ co ordinates into the queue. We need them as discussed above!
2. Also keep a counter for fresh oranges! We need to eat them all as discussed above! Also keep a counter for minutes passed
3. Keep removing the element from the queue, and explore them in all the 4 directions. Keep an out of bounds check.
4. If the cell popped from the queue is at the edge, its neighbor's in some direction might get out of bounds. Just move ahead of that guy, don’t consider it all. Also ignore if that neighbor is already rotten, or is a safe place.
5. Otherwise, turn that fresh orange into a rotten one (mutate) reduce fresh count! You just ate that up! Also now this guy is rotten, so we can explore this too (later on) So append this to the queue (Append)
6. Now if your fresh oranges are = 0. The return the minutes passed! Else return a -1 saying you could not rotten the entire field :)

Before I give the code there are two things that I will be using in the next posts about BFS questions, they’ll be used again and again:

1. Exploring directions:

[(1,0), (-1,0), (0,1), (0,-1)] represent the four directions. For each element coming from the queue, this is how we will look around it. Also we do boundary checks as explained in the code below

x,y = queue.popleft()
for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
  xx, yy = x + dx, y + dy
  if xx < 0 or xx == rows or yy < 0 or yy == cols:
      continue

2. Mutate and Append

This is a key step for such BFS based questions, we make changes in our actual grid, and then we need to process this new change that we have made

 # mark the current fresh orange as rotten
 grid[xx][yy] = 2
 
 # add the current rotten to the queue
 rotten.append((xx, yy))

FINAL CODE

Hope this was helpful. Next I will be picking up this question https://leetcode.com/problems/as-far-from-land-as-possible/

Any suggestions are welcome :)