Multisource BFS for your FAANG coding interviews

This is a neat little trick to optimize your code and reach peak performance

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…

Spot Graphs in your coding interviews

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.

BFS goes level by level. There is no reason we can’t add multiple nodes (gates) to the first level. There’s your hint. Try to work this out for yourself before proceeding

Important Points

1. 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?

1. 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.
2. 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.
3. 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

Photo by Alina Grubnyak on Unsplash

If you liked this write-up, you would like my daily email newsletter Technology Made Simple. It covers topics in Algorithm Design, Math, AI, Data Science, Recent Events in Tech, Software Engineering, and much more to make you a better developer. I am currently running a 20% discount for a WHOLE YEAR, so make sure to check it out. Using this discount will drop the prices-

800 INR (10 USD) → 533 INR (8 USD) per Month

8000 INR (100 USD) → 6400INR (80 USD) per year

You can learn more about the newsletter here

Reach out to me

Use the links below to check out my other content, learn more about tutoring, or just to say hi. Also, check out the free Robinhood referral link. We both get a free stock (you don’t have to put any money), and there is no risk to you. So not using it is just losing free money.

To help me understand you fill out this survey (anonymous)

Check out my other articles on Medium. : https://rb.gy/zn1aiu

My YouTube: https://rb.gy/88iwdd

Reach out to me on LinkedIn. Let’s connect: https://rb.gy/m5ok2y

My Instagram: https://rb.gy/gmvuy9

My Twitter: https://twitter.com/Machine01776819

If you’re looking to build a career in tech: https://codinginterviewsmadesimple.substack.com/

Get a free stock on Robinhood: https://join.robinhood.com/fnud75