Jobs

Interviews

Discussions

All Paths from Source Lead to Destination

Medium

Asked by:

15 views

Topics:

GraphsRecursion

Given a directed acyclic graph (DAG) with n vertices labeled from 0 to n - 1, and an array of directed edges graph where graph[i] = [ui, vi] represents a directed edge from node ui to node vi.

Return true if and only if:

For each possible starting node, there is a path from the starting node to the destination.
When you reach the destination, you can not leave the destination.

Example 1:

Input: n = 3, graph = [[0,1],[0,2]]
Output: false
Explanation: Not all paths from vertex 0 leads to vertex 2.  One possible path is 0 -> 1.

Example 2:

Input: n = 4, graph = [[0,1],[0,2],[1,3],[2,3]]
Output: true

Example 3:

Input: n = 4, graph = [[0,1],[0,3],[1,2],[2,1]]
Output: false
Explanation: There is a cycle between 1 and 2.

Constraints:

1 <= n <= 10⁴
0 <= graph.length <= 10⁴
graph[i].length == 2
0 <= ui, vi <= n - 1
ui != vi
All the pairs [ui, vi] are distinct.
The given graph is a directed acyclic graph (DAG).

Try coding it in LeetCode

All Paths from Source Lead to Destination

Medium

Asked by:

15 views

Topics:

GraphsRecursion

Return true if and only if:

For each possible starting node, there is a path from the starting node to the destination.
When you reach the destination, you can not leave the destination.

Example 1:

Input: n = 3, graph = [[0,1],[0,2]]
Output: false
Explanation: Not all paths from vertex 0 leads to vertex 2.  One possible path is 0 -> 1.

Example 2:

Input: n = 4, graph = [[0,1],[0,2],[1,3],[2,3]]
Output: true

Example 3:

Input: n = 4, graph = [[0,1],[0,3],[1,2],[2,1]]
Output: false
Explanation: There is a cycle between 1 and 2.

Constraints:

1 <= n <= 10⁴
0 <= graph.length <= 10⁴
graph[i].length == 2
0 <= ui, vi <= n - 1
ui != vi
All the pairs [ui, vi] are distinct.
The given graph is a directed acyclic graph (DAG).

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the graph represented as an adjacency list or an adjacency matrix? If it's an adjacency list, what data type does it use to store neighbors?
Are cycles allowed in the graph? If so, should cycles be considered as paths that do not lead to the destination?
Is the graph guaranteed to be a directed acyclic graph (DAG)?
Is the destination node guaranteed to be reachable from the source node?
What should I return if the graph is empty or if the source and destination nodes are the same?

Brute Force Solution

Approach

Imagine you're exploring a maze with lots of paths. The brute force approach means trying absolutely every possible route from the start. We continue exploring each route until we either reach the destination or find a dead end.

Here's how the algorithm would work step-by-step:

Begin at the starting point.
Explore one path leading out of the starting point.
Keep following that path. At each fork in the road, choose one way to go and remember the other options you didn't pick.
If you arrive at the destination, remember this path.
If you hit a dead end, go back to the last fork in the road and try a different path.
Repeat these steps, exploring every single possible path from the starting point.
Once you've explored every path, check if all the paths that eventually terminated, ended up at the destination.

Code Implementation

def all_paths_lead_to_destination_brute_force(number_of_nodes, edges, source, destination):

    graph = [[] for _ in range(number_of_nodes)]
    for source_node, destination_node in edges:
        graph[source_node].append(destination_node)

    all_paths = []

    def find_all_paths(current_node, current_path):
        current_path = current_path + [current_node]

        if not graph[current_node]:
            all_paths.append(current_path)
            return

        for neighbor in graph[current_node]:
            find_all_paths(neighbor, current_path)

    find_all_paths(source, [])

    if not all_paths:
        if source == destination:
            return True
        else:
            return False

    # Check if all paths lead to the destination node

    for path in all_paths:
        if path[-1] != destination:
            return False

    # Need to ensure no path dead ends before the destination
    for path in all_paths:
        if len(path) > 1:
            for node_index in range(len(path) -1 ):
                node = path[node_index]
                if not graph[node]:
                    return False

    return True

Big(O) Analysis

Time Complexity

O(V!) – The provided brute force approach explores all possible paths in the graph. In the worst-case scenario, the graph can have a structure where visiting all vertices is required to explore all paths from the source. Since we are exploring all paths from a single source, with V being the number of vertices, the number of paths we explore could grow factorially. The algorithm effectively performs a depth-first search where each vertex can lead to multiple other vertices, resulting in a time complexity proportional to the number of possible paths, which is O(V!).

Space Complexity

O(N) – The provided plain English explanation outlines a depth-first search approach. In the worst-case scenario, the algorithm might explore a path that visits all N nodes in the graph before reaching a dead end or the destination. This exploration will result in a recursion stack depth of N, where N is the number of nodes in the graph, as each call remembers the state of exploring a certain node and its adjacent edges. Each recursive call consumes a fixed amount of memory for local variables and function parameters. Therefore, the auxiliary space complexity due to the recursion stack is O(N).

Optimal Solution

Approach

This problem asks us to check if all paths from a starting point in a graph lead to a specific destination. The optimal approach cleverly combines checking if a destination is reachable with identifying cycles that prevent guaranteed arrival at the destination.

Here's how the algorithm would work step-by-step:

First, check if the graph even has a destination node. If there isn't one, we can't possibly reach it from every starting point.
Next, start from the source node and explore the graph's paths, marking nodes as 'visiting' while you're on a path and 'visited' once you're done exploring from them.
If you encounter a node that is currently marked 'visiting', this means you've found a cycle, which means some path doesn't lead to the destination, so return 'false'.
If you reach a node with no outgoing edges (a dead end) and it's not the destination, then some path doesn't lead to the destination, so return 'false'.
If you reach the destination, mark it as visited and continue exploring other paths.
If you have explored all paths from the source without finding a cycle or a dead end that isn't the destination, return 'true'.

Code Implementation

def all_paths_lead_to_destination(number_of_nodes, edges, destination_node):
    graph = [[] for _ in range(number_of_nodes)]
    for source_node, target_node in edges:
        graph[source_node].append(target_node)

    # If destination has outgoing edges, no
    if graph[destination_node]:
        return False

    visited = [0] * number_of_nodes

    def dfs(current_node):
        # If cycle, some path won't reach dest.
        if visited[current_node] == 1:
            return False

        # If already visited, skip.
        if visited[current_node] == 2:
            return True

        visited[current_node] = 1

        # If it is a dead end.
        if not graph[current_node]:
            # Dead end should be the destination.
            if current_node != destination_node:
                return False
        else:
            for neighbor in graph[current_node]:
                if not dfs(neighbor):
                    return False

        # Mark as completely visited.
        visited[current_node] = 2
        return True

    # Check if all paths from source reach dest.
    return dfs(0)

Big(O) Analysis

Time Complexity

O(V + E) – The time complexity is determined by the depth-first search (DFS) traversal of the graph. In the worst case, we might visit every vertex (node) and every edge once. V represents the number of vertices and E represents the number of edges in the graph. The 'visiting' and 'visited' sets ensure that each node is processed at most once. Therefore, the overall time complexity is O(V + E).

Space Complexity

O(N) – The algorithm uses a 'visiting' and 'visited' set to keep track of nodes during the Depth-First Search (DFS). In the worst-case scenario, where the graph is a single path, all N nodes could be in the 'visiting' set simultaneously (during recursion), or eventually in the 'visited' set. Therefore, the space required for these sets scales linearly with the number of nodes, N. This means the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Empty graph (n = 0)	Return true because there are no paths to violate the condition.
Graph with only one node (n = 1) and no edges	Return true if the destination is that single node; false otherwise.
Source node is same as destination node, and it has no outgoing edges.	Return true because all paths trivially lead to the destination (itself).
Source node is same as destination node, and it has a self-loop.	Return true because all paths (including infinitely looping ones) lead to the destination.
Graph contains a cycle that does not lead to the destination.	Return false as paths following the cycle will not reach the destination.
Graph contains a cycle that does lead to the destination.	This is acceptable as long as all paths, including those within the cycle, eventually lead to the destination.
Destination node has outgoing edges.	Return false as there is a path from the destination that doesn't end in the destination.
Graph contains disconnected components, source component does not reach destination.	Return false, because the components not connected to the destination will not lead to it.

Empty graph (n = 0)

How to Handle:

Return true because there are no paths to violate the condition.

Graph with only one node (n = 1) and no edges

How to Handle:

Return true if the destination is that single node; false otherwise.

Source node is same as destination node, and it has no outgoing edges.

How to Handle:

Return true because all paths trivially lead to the destination (itself).

Source node is same as destination node, and it has a self-loop.

How to Handle:

Return true because all paths (including infinitely looping ones) lead to the destination.

Graph contains a cycle that does not lead to the destination.

How to Handle:

Return false as paths following the cycle will not reach the destination.

Graph contains a cycle that *does* lead to the destination.

How to Handle:

This is acceptable as long as *all* paths, including those within the cycle, eventually lead to the destination.

Destination node has outgoing edges.

How to Handle:

Return false as there is a path from the destination that doesn't end in the destination.

Graph contains disconnected components, source component does not reach destination.

How to Handle:

Return false, because the components not connected to the destination will not lead to it.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Is the graph represented as an adjacency list or an adjacency matrix? If it's an adjacency list, what data type does it use to store neighbors?
Are cycles allowed in the graph? If so, should cycles be considered as paths that do not lead to the destination?
Is the graph guaranteed to be a directed acyclic graph (DAG)?
Is the destination node guaranteed to be reachable from the source node?
What should I return if the graph is empty or if the source and destination nodes are the same?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Begin at the starting point.
Explore one path leading out of the starting point.
Keep following that path. At each fork in the road, choose one way to go and remember the other options you didn't pick.
If you arrive at the destination, remember this path.
If you hit a dead end, go back to the last fork in the road and try a different path.
Repeat these steps, exploring every single possible path from the starting point.
Once you've explored every path, check if all the paths that eventually terminated, ended up at the destination.

Code Implementation

def all_paths_lead_to_destination_brute_force(number_of_nodes, edges, source, destination):

    graph = [[] for _ in range(number_of_nodes)]
    for source_node, destination_node in edges:
        graph[source_node].append(destination_node)

    all_paths = []

    def find_all_paths(current_node, current_path):
        current_path = current_path + [current_node]

        if not graph[current_node]:
            all_paths.append(current_path)
            return

        for neighbor in graph[current_node]:
            find_all_paths(neighbor, current_path)

    find_all_paths(source, [])

    if not all_paths:
        if source == destination:
            return True
        else:
            return False

    # Check if all paths lead to the destination node

    for path in all_paths:
        if path[-1] != destination:
            return False

    # Need to ensure no path dead ends before the destination
    for path in all_paths:
        if len(path) > 1:
            for node_index in range(len(path) -1 ):
                node = path[node_index]
                if not graph[node]:
                    return False

    return True

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, check if the graph even has a destination node. If there isn't one, we can't possibly reach it from every starting point.
Next, start from the source node and explore the graph's paths, marking nodes as 'visiting' while you're on a path and 'visited' once you're done exploring from them.
If you encounter a node that is currently marked 'visiting', this means you've found a cycle, which means some path doesn't lead to the destination, so return 'false'.
If you reach a node with no outgoing edges (a dead end) and it's not the destination, then some path doesn't lead to the destination, so return 'false'.
If you reach the destination, mark it as visited and continue exploring other paths.
If you have explored all paths from the source without finding a cycle or a dead end that isn't the destination, return 'true'.

Code Implementation

def all_paths_lead_to_destination(number_of_nodes, edges, destination_node):
    graph = [[] for _ in range(number_of_nodes)]
    for source_node, target_node in edges:
        graph[source_node].append(target_node)

    # If destination has outgoing edges, no
    if graph[destination_node]:
        return False

    visited = [0] * number_of_nodes

    def dfs(current_node):
        # If cycle, some path won't reach dest.
        if visited[current_node] == 1:
            return False

        # If already visited, skip.
        if visited[current_node] == 2:
            return True

        visited[current_node] = 1

        # If it is a dead end.
        if not graph[current_node]:
            # Dead end should be the destination.
            if current_node != destination_node:
                return False
        else:
            for neighbor in graph[current_node]:
                if not dfs(neighbor):
                    return False

        # Mark as completely visited.
        visited[current_node] = 2
        return True

    # Check if all paths from source reach dest.
    return dfs(0)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty graph (n = 0)	Return true because there are no paths to violate the condition.
Graph with only one node (n = 1) and no edges	Return true if the destination is that single node; false otherwise.
Source node is same as destination node, and it has no outgoing edges.	Return true because all paths trivially lead to the destination (itself).
Source node is same as destination node, and it has a self-loop.	Return true because all paths (including infinitely looping ones) lead to the destination.
Graph contains a cycle that does not lead to the destination.	Return false as paths following the cycle will not reach the destination.
Graph contains a cycle that does lead to the destination.	This is acceptable as long as all paths, including those within the cycle, eventually lead to the destination.
Destination node has outgoing edges.	Return false as there is a path from the destination that doesn't end in the destination.
Graph contains disconnected components, source component does not reach destination.	Return false, because the components not connected to the destination will not lead to it.

Empty graph (n = 0)

How to Handle:

Return true because there are no paths to violate the condition.

Graph with only one node (n = 1) and no edges

How to Handle:

Return true if the destination is that single node; false otherwise.

Source node is same as destination node, and it has no outgoing edges.

How to Handle:

Return true because all paths trivially lead to the destination (itself).

Source node is same as destination node, and it has a self-loop.

How to Handle:

Return true because all paths (including infinitely looping ones) lead to the destination.

Graph contains a cycle that does not lead to the destination.

How to Handle:

Return false as paths following the cycle will not reach the destination.

Graph contains a cycle that *does* lead to the destination.

How to Handle:

This is acceptable as long as *all* paths, including those within the cycle, eventually lead to the destination.

Destination node has outgoing edges.

How to Handle:

Return false as there is a path from the destination that doesn't end in the destination.

Graph contains disconnected components, source component does not reach destination.

How to Handle:

Return false, because the components not connected to the destination will not lead to it.