Multi-Source BFS [Technique Tuesday]
This is a neat little trick to optimize your code and reach peak performance
To learn more about the newsletter, check our detailed About Page + FAQs
To help me understand you better, please fill out this anonymous, 2-min survey. If you liked this post, make sure you hit the heart icon in this email.
Recommend this publication to Substack over here
Take the next step by subscribing here
Graph problems are annoying enough as is.
But sometimes, the standard stuff isn’t enough. Sure it can help you get to a solution, but it’s not close to the optimal solution. Sometimes you need a lil extra something. This post will cover one such variant.
Let’s say your prep is amazing. You’ve gone through my articles on Graphs, and are an expert at the Graph Spotting framework (check out the post below). You can look at the problem and find the best traversal algorithm. Your skills are certified. But there’s a problem…
What do you do when you have to run a BFS from a bunch of locations to find the answer? You can visit the starting nodes one by one, but that is slow. Is there a better solution? Enter the Multi-Source BFS.
Important Points
BFS Refresher- Traditional BFS starts with a single source i.e, a single node at level 1 (distance 0). Let’s look at the logic for BFS for distance mapping
Initialize queue Q Initialize array d[N] = [INF]*len(Nodes) #for distances from source Q.enqueue(a) distance = 0 d[a] = 0 while Q is not empty: n = Q.dequeue distance = distance + 1 for each neighbor n_i of n: if d[n_i] is infinity: d[n_i] = distance Q.enqueue(n_i)
Traditional BFS can handle distance finding from one node. What can do to adapt to more nodes?
Multi-Source BFS- As the name suggests, we change the sources. The source node is the original node we start from (a in the pseudo code). If we have multiple starting locations for our BFS, there is nothing stopping us from appending all those locations into our starting queue. Everything else is usual.
If you’re confused- If this is confusing you, feel to take a breather. Consider your vanilla BFS. Once you have populated your queue with the neighbors of your source, you can basically treat the queue as a list of sources starting on the subgraph. This is because graphs and BFS are inherently recursive. The only difference between the vanilla and a multi-source BFS is that the latter has a populated queue at time/distance 0. This is one of the coolest properties of recursive structures. Even more complex variants of a simple recursive structure can be reduced to your simple structure easily. This is why recursive code is often called elegant. There’s a cool topic to bring up at parties where you’re surrounded by nerds.
Code for you- If you’re having trouble with this concept, it might be helpful to see how it is implemented. Here you can see the Python code for the Microsoft favorite question, Rotting Oranges, which we covered here. Try to break the code into different chunks to differentiate it into steps. This will help you build up your familiarity with this idea.
from collections import deque class Solution: def orangesRotting(self, grid: List[List[int]]) -> int: rotten_orange = deque() minutes = 0 fresh_orange = 0 rows, cols = len(grid), len(grid[0]) for r in range(rows): for c in range(cols): orange = grid[r][c] if orange == 2: rotten_orange.append((r,c)) elif orange == 1: fresh_orange += 1 directions = [(1,0), (-1,0), (0, 1), (0,-1)] while rotten_orange and fresh_orange > 0: minutes += 1 for _ in range(len(rotten_orange)): r, c = rotten_orange.popleft() for dr, dc in directions: row = r + dr col = c + dc if row >= 0 and row < rows and col >= 0 and col < cols and grid[row][col] == 1: fresh_orange -= 1 grid[row][col] = 2 rotten_orange.append((row, col)) return minutes if fresh_orange == 0 else -1
I created Technology Interviews Made Simple using new techniques discovered through tutoring multiple people into top tech firms. The newsletter is designed to help you succeed, saving you from hours wasted on the Leetcode grind. I have a 100% satisfaction policy, so you can try it out at no risk to you. You can read the FAQs and find out more here. Use the button below to get 20% off for upto a whole year.
Before proceeding, if you have enjoyed this post so far, please make sure you like it (the little heart button in the email/post). I also have a special request for you.
***Special Request***
This newsletter has received a lot of love. If you haven’t already, I would really appreciate it if you could take 5 seconds to let Substack know that they should feature this publication on their pages. This will allow more people to see the newsletter.
There is a simple form in Substack that you can fill up for it. Here it is. Thank you.
https://docs.google.com/forms/d/e/1FAIpQLScs-yyToUvWUXIUuIfxz17dmZfzpNp5g7Gw7JUgzbFEhSxsvw/viewform
To get your Substack URL, follow the following steps-
Open - https://substack.com/
If you haven’t already, log in with your email.
In the top right corner, you will see your icon. Click on it. You will see the drop-down. Click on your name/profile. That will show you the link.
You will be redirected to your URL. Please put that in to the survey. Appreciate your help.
In the comments below, share what topic you want to focus on. I’d be interested in learning and will cover them. To learn more about the newsletter, check our detailed About Page + FAQs
If you liked this post, make sure you fill out this survey. It’s anonymous and will take 2 minutes of your time. It will help me understand you better, allowing for better content.
https://forms.gle/XfTXSjnC8W2wR9qT9
I see you living the dream.
Go kill all and Stay Woke,
Devansh <3
To make sure you get the most out of Technique Tuesdays, make sure you’re checking in the rest of the days as well. Leverage all the techniques I have discovered through my successful tutoring to easily succeed in your interviews and save your time and energy by joining the premium subscribers down below. Get a discount (for a whole year) using the button below
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my Machine Learning breakdowns: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75