Graph Coding Question - All Paths From Source To Target (LeetCode)

Here is a step by step explanation of a graph question involving breadth first search! Check out my interview prep platform for learning the patterns! 📢 Interview Prep Platform: https://algoswithmichael.com/ 🎧 Join the community Discord: https://discord.gg/aVWsAaaCtT 💰 Support me on Patreon: https://www.patreon.com/michaelmuinos 🔗Follow me on LinkedIn: https://www.linkedin.com/in/michael-muinos 📂Follow me on Github: https://github.com/MichaelMuinos In this video, I explain a popular graph coding question asked at Bloomberg. For this problem, we are given a 2D array represented as a graph and we must find all possible paths from node 0 to node n - 1 where n is the length of our input array. To solve this problem, we can use either a Depth-First Search or Breadth-First Search. The explanation I go over involves BFS and that means we must utilize a queue. Starting from node 0, we add in a list of integers inside of our queue representing the paths we have taken up to that point. As we poll from the queue, the last node in the list is the node we must continue our BFS on. If the last node in the list is node n - 1, then we have successfully found a path going from our source to target and we add that list inside of our result. The time complexity of this solution is O(N^2 * 2^N) where N is the number of nodes we have in our graph. The 2^N comes from the fact that for each path and for every node we can either 1) add the node in the path or 2) don't add the node in the path resulting in a combination of paths summing to 2^N. The space complexity is O(2^N) since in the worst case we must add all paths inside of our result which is then returned from our function.

• #science_technology
• #coding
• #software_engineering