Find Eventual Safe States
Problem Highlights
- 🔗 Leetcode Link: Find Eventual Safe States
- 💡 Problem Difficulty: Medium
- ⏰ Time to complete: __ mins
- 🛠️ Topics: Graphs, Depth-First Search, Breadth-First Search, Topological Sort
- 🗒️ Similar Questions: Build a Matrix With Conditions
1: U-nderstand
Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
- What do we need to do with the nodes?
- This question is about to find the nodes who is not in a cycle, which means itself and its children are not in a cycle.
- What are 4 states we can use to record a node’s status?
- We take 4 states to record a node’s status: {UNKNOWN, VISIT, SAFE, UNSAFE}. UNKNOWN: current node is not visited. Initialized status. VISIT: current node is in the process of dfs. SAFE: current node is safe. All children are SAFE -> current is SAFE. UNSAFE: current node is unsafe.
- What do we do to nodes that are eventually safe?
- Return them as an array in sorted order.
HAPPY CASE
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.
EDGE CASE
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.
2: M-atch
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
For graph problems, some things we want to consider are:
- DFS: A node is eventually safe if and only if no path starting from it can reach a cycle. We can detect this with a depth-first search that marks each node with one of three states: unvisited, visiting (currently on the DFS path), and safe. If the DFS ever revisits a node marked visiting, we have found a cycle and every node on that path is unsafe; a node is marked safe only after all of its outgoing edges have been shown to lead to safe nodes.
- BFS / Topological Sort: We can reverse every edge and run a topological sort (Kahn’s algorithm) on the reversed graph. Terminal nodes (no outgoing edges in the original graph) are safe, so they seed the queue; each time we remove a safe node, we decrement the remaining out-degree of the original-graph nodes that point to it, and any node whose outgoing edges have all been accounted for is also safe.
- Adjacency List: We can use an adjacency list to store the graph, especially when the graph is sparse.
- Adjacency Matrix: We can use an adjacency matrix to store the graph, but a sparse graph will cause an unneeded worst-case runtime.
- Map: We can use a map to store each node’s outgoing edges for quick neighbor lookup during traversal.
- Union Find: Are there find and union operations here? Can you perform a find operation where you can determine which subset a particular element is in? This can be used for determining if two elements are in the same subset. Can you perform a union operation where you join two subsets into a single subset? Can you check if the two subsets belong to same set? If no, then we cannot perform union.
3: P-lan
Plan the solution with appropriate visualizations and pseudocode.
General Idea: In a directed graph, we start at some node and every turn, walk along a directed edge of the graph. If we reach a node that is terminal (that is, it has no outgoing directed edges), we stop. Now, say our starting node is eventually safe if and only if we must eventually walk to a terminal node. More specifically, there exists a natural number K so that for any choice of where to walk, we must have stopped at a terminal node in less than K steps.
The directed graph has N nodes with labels 0, 1, …, N-1, where N is the length of graph. The graph is given in the following form: graph[i] is a list of labels j such that (i, j) is a directed edge of the graph. NOTE that we may do some pruning optimization.
To know if the path is not safe, we check if it goes back to the ongoing path. Therefore, I have a set visiting to store nodes that are in the current DFS. I make sure to remove the node once DFS finishes.
1. When we visit a node, the only possibilities are that we’ve marked the entire subtree black (which must be eventually safe), or it has a cycle and we have only marked the members of that cycle gray. So the invariant that gray nodes are always part of a cycle, and black nodes are always eventually safe is maintained.
2. In order to exit our search quickly when we find a cycle (and not paint other nodes erroneously), we’ll say the result of visiting a node is true if it is eventually safe, otherwise false. This allows information that we’ve reached a cycle to propagate up the call stack so that we can terminate our search early.
⚠️ Common Mistakes
- The crux of the problem is whether you can reach a cycle from the node you start in. If you can, then there is a way to avoid stopping indefinitely; and if you can’t, then after some finite number of steps you’ll stop. Thinking about this property more, a node is eventually safe if all its outgoing edges are to nodes that are eventually safe.
We start with nodes that have no outgoing edges - those are eventually safe. Now, we can update any nodes which only point to eventually safe nodes - those are also eventually safe. Then, we can update again, and so on.
However, we’ll need a good algorithm to make sure our updates are efficient.
4: I-mplement
Implement the code to solve the algorithm.
class Solution:
def eventualSafeNodes(self, graph: List[List[int]]) -> List[int]:
dt = defaultdict(list)
status = defaultdict(int) # if visiting this node change status to 1 else 0
res = []
for i, val in enumerate(graph):
dt[i] = val
def dfs(num):
if dt[num] == []: return True
if status[num] == 1: return False
status[num] = 1
for val in dt[num]:
if not dfs(val):
return False
dt[num] = []
status[num] = 0
return True
for num in range(len(graph)):
if dfs(num):
res.append(num)
return res
class Solution {
public List<Integer> eventualSafeNodes(int[][] graph) {
List<Integer> res = new ArrayList<>();
int n = graph.length; //number of nodes
int[] visited = new int[n]; //3 status, 0: unvisited, 1: visiting, 2: visited
for (int i = 0; i < n; i++) // try all nodes
if (DFS(graph, i, visited))
res.add(i);
return res;
}
//return true if node i is safe
private boolean DFS(int[][] graph, int i, int[] visited) {
if (visited[i] == 1) //node i is being visited, so cycle
return false;
visited[i] = 1; //visiting
for (int neighbor : graph[i]) {
int status = visited[neighbor]; //status of neighbor
if (status == 1) //neighbor is a node we are visiting, so cycle. All node in a cycle is not safe
return false;
if (status == 2) //already visited
continue;
//otherwise, status == 0, meaning ok to visit
if (!DFS(graph, neighbor, visited))
return false;
}
visited[i] = 2; //visited
return true;
}
}
5: R-eview
Review the code by running specific example(s) and recording values (watchlist) of your code’s variables along the way.
- Trace through your code with an input to check for the expected output
- Catch possible edge cases and off-by-one errors and verify the code works for the happy and edge cases you created in the “Understand” section
6: E-valuate
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Time Complexity - O(V + E)
Space Complexity - O(V + E)