Code Implementation

class Solution:
    def leadsToDestination(self, n, edges, source, destination):
        from collections import defaultdict

        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)

        visited = [0] * n  # 0 = unvisited, 1 = visiting, 2 = visited

        def dfs(node):
            if visited[node] == 1:
                return False  # found a cycle
            if visited[node] == 2:
                return True   # already checked

            if not graph[node]:
                return node == destination

            visited[node] = 1
            for nei in graph[node]:
                if not dfs(nei):
                    return False
            visited[node] = 2
            return True

        return dfs(source)
      

class Solution {
public:
    bool leadsToDestination(int n, vector<vector<int>>& edges, int source, int destination) {
        vector<vector<int>> graph(n);
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
        }
        vector<int> visited(n, 0); // 0 = unvisited, 1 = visiting, 2 = visited

        function<bool(int)> dfs = [&](int node) {
            if (visited[node] == 1) return false; // cycle
            if (visited[node] == 2) return true;  // already checked
            if (graph[node].empty()) return node == destination;

            visited[node] = 1;
            for (int nei : graph[node]) {
                if (!dfs(nei)) return false;
            }
            visited[node] = 2;
            return true;
        };

        return dfs(source);
    }
};
      

class Solution {
    public boolean leadsToDestination(int n, int[][] edges, int source, int destination) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (int[] edge : edges) {
            graph.get(edge[0]).add(edge[1]);
        }
        int[] visited = new int[n]; // 0 = unvisited, 1 = visiting, 2 = visited

        return dfs(graph, visited, source, destination);
    }

    private boolean dfs(List<List<Integer>> graph, int[] visited, int node, int dest) {
        if (visited[node] == 1) return false;
        if (visited[node] == 2) return true;
        if (graph.get(node).isEmpty()) return node == dest;

        visited[node] = 1;
        for (int nei : graph.get(node)) {
            if (!dfs(graph, visited, nei, dest)) return false;
        }
        visited[node] = 2;
        return true;
    }
}
      

var leadsToDestination = function(n, edges, source, destination) {
    const graph = Array.from({length: n}, () => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
    }
    const visited = new Array(n).fill(0); // 0 = unvisited, 1 = visiting, 2 = visited

    function dfs(node) {
        if (visited[node] === 1) return false; // cycle
        if (visited[node] === 2) return true;  // already checked
        if (graph[node].length === 0) return node === destination;

        visited[node] = 1;
        for (const nei of graph[node]) {
            if (!dfs(nei)) return false;
        }
        visited[node] = 2;
        return true;
    }

    return dfs(source);
};
      

Problem Description

You are given a directed graph with n nodes, labeled from 0 to n - 1. The graph is represented by a list of edges, where each edge is a pair [u, v] indicating a directed edge from node u to node v.

You are also given two nodes: source and destination. The task is to determine whether every possible path starting from source eventually leads to destination, with the following constraints:

• If a path reaches a node with no outgoing edges, that node must be destination (otherwise, the path "gets stuck" and fails).
• The graph may contain cycles. Paths that enter a cycle and never reach destination are not valid.
• There may be multiple outgoing edges from a node, and you must ensure all possible paths lead to destination.

In summary, you must check that all paths from source either end up at destination or do not get stuck or trapped in cycles.

Thought Process

At first glance, the problem seems to ask for a simple path search from source to destination. However, the requirement that all possible paths must lead to destination makes it much more challenging.

A brute-force approach would be to enumerate every possible path from source and check if each one ends at destination. But this is impractical for large graphs, especially with cycles, as the number of paths can be exponential or even infinite.

The key realization is that we need to:

• Detect if any path gets stuck at a node other than destination.
• Detect if any path falls into a cycle (which would mean paths could run forever without reaching destination).

Solution Approach

To solve this problem efficiently, we can use Depth-First Search (DFS) with cycle detection and memoization. Here’s how we can break it down:

1. Build the graph:
   • Represent the graph as an adjacency list for fast lookups.
2. Track node states:
   • For each node, keep track of its visiting state:
     • 0 = unvisited
     • 1 = currently visiting (in the call stack)
     • 2 = fully visited (all paths from here are already checked)
3. DFS with cycle and dead-end checks:
   • Start DFS from source.
   • If we visit a node marked as 1, we've found a cycle—return False.
   • If we reach a node with no outgoing edges, check if it is destination. If not, return False (dead end).
   • For every neighbor, recursively check that all paths from there also lead to destination.
   • After all neighbors are checked, mark the node as 2 to memoize the result.
4. Return the result:
   • If any path fails the above checks, return False. If all pass, return True.

Using this approach, we avoid redundant work by memoizing nodes we've already checked, and we prevent infinite loops by detecting cycles with the "visiting" state.

Example Walkthrough

Let's consider an example:

    n = 4
    edges = [[0,1],[0,2],[1,3],[2,3]]
    source = 0
    destination = 3
  

1. Start DFS from node 0. It has two neighbors: 1 and 2.
2. DFS to 1:
   • 1 has neighbor 3. 3 has no outgoing edges and is the destination—valid path.
3. DFS to 2:
   • 2 has neighbor 3. Again, valid path.
4. All paths from 0 lead to 3, so the answer is True.

If, for example, edges = [[0,1],[1,0]] (a cycle between 0 and 1), and destination = 1, starting from 0 would result in an infinite loop, so the answer would be False.

Time and Space Complexity

Brute-force approach:

• Enumerating all possible paths can take exponential time, especially with cycles.

• Time Complexity: O(N + E), where N is the number of nodes and E is the number of edges. Each node and edge is traversed at most once, thanks to memoization.
• Space Complexity: O(N + E) for the adjacency list and visited state array. The recursion stack can be up to O(N) in the worst case (for a long path).

This makes the optimized solution efficient even for large graphs, as we avoid redundant traversals and infinite recursion.

Summary

In this problem, we learned to check whether all possible paths from a source node in a directed graph eventually lead to a specific destination, without getting stuck or falling into cycles. The core insight is to use DFS with state tracking to detect cycles and dead ends, while memoizing results to prevent redundant work. This approach is both efficient and robust, handling even complex graphs with cycles or multiple branches.

By understanding the constraints and designing our algorithm to check all possible paths, we ensure correctness and efficiency, making this solution both elegant and practical.