Find Final Destination

Overview

The problem asks us to traverse a directed graph starting from a specific node start until we reach a "sink" node—a node that has no outgoing edges. We are guaranteed that the graph is a Directed Acyclic Graph (DAG) and that a unique destination is reachable from our starting point.

The core intuition is to treat this as a path-following problem. Since every node in our path (except the destination) has exactly one transition we care about to reach the goal, we simply need an efficient way to look up "Where do I go next from here?"

Brute Force

A brute-force approach involves searching through the entire list of edges every time we want to move to the next node. We start at current = start, then iterate through the edges list to find an edge where the source matches current. If we find it, we update current to the target of that edge and repeat the process. If we scan the entire list and find no such edge, we have reached the destination.

def find_destination(edges: list[list[str]], start: str) -> str:
    current = start
    while True:
        found_next = False
        for u, v in edges:
            if u == current:
                current = v
                found_next = True
                break
        
        if not found_next:
            return current

Time complexity: O(N * L) — Where N is the number of nodes in the path and L is the length of the edges list; we potentially scan all edges for every step taken. Space complexity: O(1) — We only store the current node string and a few loop variables.

Optimal / Best Approach

The bottleneck in the brute-force approach is the repeated O(L) scan of the edges list. We can optimize this by pre-processing the edges into a Hash Map (dictionary in Python).

Since we are guaranteed a unique path and no cycles, each node we encounter during the traversal will have at most one outgoing edge that leads toward the destination. By mapping source -> target, we can achieve O(1) lookups for the next node.

1. Create a dictionary graph where graph[u] = v for every edge [u, v].
2. Set current = start.
3. While current exists as a key in our graph dictionary, update current to graph[current].
4. Return current.

def find_destination(edges: list[list[str]], start: str) -> str:
    # Pre-process edges into a adjacency map for O(1) lookup
    # Note: Because the destination is unique and reachable, 
    # we only need to store one target per source.
    mapping = {u: v for u, v in edges}
    
    current = start
    # Traverse until we reach a node that isn't a source in our mapping
    while current in mapping:
        current = mapping[current]
        
    return current

Time complexity: O(E) — Where E is the number of edges. We iterate through the edges once to build the map, and then traverse the path (which is at most E nodes). Space complexity: O(E) — We store the edges in a dictionary to allow for fast lookups.

Why this works

• Acyclic Guarantee: Because the graph is acyclic, we are guaranteed never to fall into an infinite loop. The while loop must eventually terminate.
• Unique Destination: The problem guarantees one reachable sink from the start. Even if the graph has multiple components or other sinks, the path from start is deterministic because we only care about the outgoing edge from our current location.
• Dictionary Efficiency: In Python, dictionary lookups are average-case O(1), making this approach significantly faster than re-scanning the list for large inputs.

Fast