Leetcode Pattern 1 | DFS + BFS == 25% of the problems — part 2

Hola again ! Thanks for all the positive feedback. It really motivates me to keep writing daily. Many people actually asked me to write on DP patterns next as that is the most dreaded topic in interview prep. I would dedicate the next few posts to the same, building intuition on some non-trivial DP problems but for today let’s complete BFS. Some useful tips for DP to help you out till then:

1. Solve 3 DP problems each day for 2 weeks and you’ll start getting a hang of the underlying patterns. Struggle a bit, think hard, lookup the solution after an hour or two, understand the intuition deeply, repeat.
2. Think hard on the classic DP problems ( which are only a handful ), discuss / explain the intuition to a peer, draw it out on paper ( very important ) and you would then be able to solve most DP problems.
3. Read solutions to DP problems from geeksforgeeks or watch Tushar Roy’s playlist on DP, the whole point is to accustom yourself with solutions to standard problems and then apply that intuition elsewhere.

Honestly DP is overrated, it is totally doable. Just break out of the ‘DP is wicked hard’ phase and start solving problems. Over the next few days I am going to follow the above outlined techniques and share some insights every day.

BFS:

Again let’s start with a tree, cause we are so obsessed with trees! level order traversal is simply a BFS and a rather simple one at that !

102. Binary Tree Level Order Traversal

The leetcode problem on level order traversal is a bit more involved than the above mentioned simple traversal. They require you to store each level result in an array and return final result as array of arrays. Just imagine somebody told you to put a line break after printing each level, that would essentially be the same problem.

1st approach

Using the above simple code it is not possible to know when a new level starts. I originally solved this problem using 2 queues, but I found this amazing approach in discuss and I have adopted it since then. (discuss is where the true learning happens ;) ). We use a dummy node as marker to mark level ends. Try visualizing the horizontal queue push- pop action going on in BFS and figure out how you could use an extra dummy node to mark level ends, then go through below code. This approach simply blew my mind !

EDIT: As Shad Khan suggested on LI, we could eliminate the dummy node using the size of queue to keep track of level. Here is his Python code:

2nd approach

Let’s play a game of 2 queues. We keep 2 queues for even and odd levels of the tree. So starting with 0th level i.e root, initialize even queue with root. Now imagine holding the even queue in your right hand and the odd queue in your left ( just 2 boxes which allow entry from only one side and exit from the opposite side).

1. Tilt your right hand so all the contents of even queue start falling out. Whenever a node falls out of a queue push it’s children into the other queue.
2. Now tilt your left hand emptying contents of odd queue and adding kids of falling out nodes into even queue.
3. Repeat until both queues are empty.

101. Symmetric Tree problem also can be solved using 2 queue method in a slightly different way, but enough with trees already! Let’s see an actual graph (matrix) problem using BFS.

542. 01 Matrix

How does one know that we need BFS here and not DFS, which is a very true dilemma is many problems, well the first thought that crosses my mind seeing this problem is if somehow I could iterate through all 0's in matrix and start a recursive action at these cells updating distances of neighboring cells by 1, keep doing so and stop only if the cell under consideration is already closer to another 0.

For this to be successful we need all those actions to execute only 1 round at a time ( visit 4 neighbors ) and then wait for all others to execute their 1 rounds so recursion doesn’t work ( DFS failed only 1 option left BFS). See how this is so similar to the tree case when we needed the kids of the current node only after we have visited nodes at same level, it’s a BFS , bingo! The reason we need this here is if we don’t wait for other actions to execute a round how would we know if the current cell is already closer to another 0 in which case we need to stop BFS operation for that cell.

Concluding thoughts on BFS :

1. Problems in which you have to find shortest path are most likely calling for a BFS.
2. For graphs having unit edge distances, shortest paths from any point is just a BFS starting at that point, no need for Dijkstra’s algorithm.
3. Maze solving problems are mostly shortest path problems and every maze is just a fancy graph so you get the flow.

Enjoy and stay tuned !