LeetCode 1059: All Paths from Source Lead to Destination

Problem Restatement

We are given a directed graph with n nodes, a source node, and a destination node.

Return true if and only if all paths from source lead to destination.

This requires:

1. Every path from source eventually reaches destination.
2. destination has no outgoing edges (it is a terminal node on all paths).

The official constraints state that 1 <= n <= 10^4 and 0 <= edges.length <= 10^4.

Input and Output

Function shape:

def leadsToDestination(n: int, edges: list[list[int]], source: int, destination: int) -> bool:
    ...

Key Insight

DFS from source. Use three states for each node:

• 0: unvisited.
• 1: currently in the DFS stack (cycle detection).
• 2: fully processed (all paths from here lead to destination).

If we visit a node in state 1, we have a cycle → return False.

If we reach a node with no outgoing edges, it must be the destination → otherwise False.

Edge Cases

• Mark nodes or cells as visited at enqueue/discovery time to avoid duplicate work.
• Return the failure value when the destination is unreachable.
• Check grid or graph boundaries before reading neighbors.

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

from collections import defaultdict

class Solution:
    def leadsToDestination(self, n: int, edges: list[list[int]], source: int, destination: int) -> bool:
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)

        state = [0] * n

        def dfs(node):
            if state[node] != 0:
                return state[node] == 2
            if not graph[node]:
                return node == destination

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

        return dfs(source)

Testing

def run_tests():
    s = Solution()

    assert s.leadsToDestination(3, [[0,1],[0,2]], 0, 2) == False
    assert s.leadsToDestination(4, [[0,1],[0,3],[1,2],[2,1]], 0, 3) == False
    assert s.leadsToDestination(4, [[0,1],[0,2],[1,3],[2,3]], 0, 3) == True

    print("all tests passed")

run_tests()