Today we will be covering a favorite of Microsoft’s. I’m sure you guys will really appreciate this problem, especially because it is great for step-step recursive problem-solving.
***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.
Problem
There is a directed graph of n
nodes with each node labeled from 0
to n - 1
. The graph is represented by a 0-indexed 2D integer array graph
where graph[i]
is an integer array of nodes adjacent to node i
, meaning there is an edge from node i
to each node in graph[i]
.
A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node.
Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.
Example 1:
Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]
Output: [2,4,5,6]
Explanation: The given graph is shown above.
Nodes 5 and 6 are terminal nodes as there are no outgoing edges from either of them.
Every path starting at nodes 2, 4, 5, and 6 all lead to either node 5 or 6.
Example 2:
Input: graph = [[1,2,3,4],[1,2],[3,4],[0,4],[]]
Output: [4]
Explanation:
Only node 4 is a terminal node, and every path starting at node 4 leads to node 4.
[FREE SUBS]To buy the solution for this problem, use any of the following links. The price is 3 USD. Once you send the payment, message me on IG, LinkedIn, Twitter, or by Email:
Venmo: https://account.venmo.com/u/FNU-Devansh
Paypal: paypal.me/ISeeThings
Or you can sign up for a Free Trial Below -
Step 1: Understanding the Structure.
As always, the first step is to read the problem well. We use specific conditions/wording, to identify ways to approach solutions. In our problem, there are two things of interest to us-
Terminal Nodes- These are defined as nodes with no outgoing edges. This would mean graph[node]=[].
Safe node- Nodes where all possible paths end in terminal nodes. When we examine what this condition means, we can come up with an interesting conclusion. For a node to be safe, it can’t be part of a cycle.
This gives us a good jumping-off point for our rough algorithm. We can traverse through our graph and try to detect cycles. If we see a node, we have already seen before, we know it’s either part of a cycle (multiple paths lead through it), or a terminal node (multiple nodes end their paths here). There is no other option.
So the next step becomes filling out the details of our algorithm.
Step 2: Figuring out the Details of our traversal
How do we figure out the correct way to traverse the graph? Luckily, I covered the framework you can use to identify the correct Graph Traversal Algorithm right here. Using the framework there, we know that DFS is likely to work really well. This is further validated by the fact that DFS is used as a base for Cycle Detection Algos. Now you know why.
So now let’s work out some of the details of our solution. We can then put our components together, to create our final solution. The reason I picked this question was that this is the perfect question to improve your coding skills without being overwhelmed.
The first step is to figure out what the skeleton of our code should look like.
Based on what we have collected so far, we can sketch out the following pseudocode-
loop through the nodes (0 to n):
if the node is safe:
add it to our list.
return list
So far, we haven’t really done much heavy lifting. And that’s okay. It is important to build solutions one step at a time, to not be overwhelmed. Now the next step is figuring out is a node is safe.
Step 3: Is Node Safe?
Next up comes our logic for figuring out if a node is safe. Since this is functionality on its own, it is best to abstract it into its own function/method. The first step of clarity is the function definition/header. Since we are trying to determine if a node is safe, it makes sense for the definition to consider that-
def isSafe(node):
What about the details of this function? Since we are using DFS, Recursion is our friend. These are the possible cases-
We have already seen this node before- We know that this means that the node is either part of a cycle or a terminal node. Either way we can easily determine whether the node is safe, and simply return that.
We have not seen this node before. Thus we must determine whether the node is safe. We know a node is safe if and only if all it’s neighbors are safe.
Thus our logic will look something like this-
if we have seen this node before-
return result( isSafe (node))
else:
loop over all neighbors(node)
if not isSafe(neighbor)
return False
#all neighbors are safe-->node is safe
result(isSafe(node))-->True
return True
Let’s turn this whole thing into code. As we do so, we will clean up this code, and figure out the little details that will make this solution run in a very efficient way.
Keep reading with a 7-day free trial
Subscribe to Technology Made Simple to keep reading this post and get 7 days of free access to the full post archives.