Quick Overview

Given a directed graph, a source and a destination, decide whether every path that starts at the source eventually stops at the destination: no reachable dead end other than the destination and no reachable cycle. It tests graph traversal, cycle detection and precise reasoning about reachability.

Check whether every path from a source node ends at a destination

Company: ByteDance

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a directed graph with `n` nodes, a `source` node and a `destination` node. Decide whether every path that starts at `source` ends at `destination`. ### Function Signature ```python def all_paths_end_at(n: int, edges: list[list[int]], source: int, destination: int) -> bool: ``` ### Rules - Nodes are numbered `0` to `n - 1`. `edges[i] = [u, v]` is a directed edge from `u` to `v`. Self-loops and repeated edges may appear. - A path starts at `source` and keeps following outgoing edges. It ends only when it reaches a node that has no outgoing edges. - Return `True` exactly when both of these hold: 1. every node reachable from `source` that has no outgoing edges is `destination`; and 2. no path from `source` can continue forever: no cycle, including a self-loop, is reachable from `source`. - `source` itself counts as reachable from `source`. If `source == destination` and that node has no outgoing edges, the answer is `True`. ### Constraints - `1 <= n <= 10^4` - `0 <= len(edges) <= 10^4` - For every edge `[u, v]`: `0 <= u, v < n`. - `0 <= source, destination < n` ### Examples **Example 1** ```text Input: n = 5, edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]], source = 0, destination = 4 Output: True ``` Both paths, `0 -> 1 -> 3 -> 4` and `0 -> 2 -> 3 -> 4`, end at node `4`, which has no outgoing edges. **Example 2** ```text Input: n = 4, edges = [[0, 1], [0, 2], [2, 3]], source = 0, destination = 3 Output: False ``` The path `0 -> 1` stops at node `1`, which has no outgoing edges and is not the destination. **Example 3** ```text Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 1], [2, 4]], source = 0, destination = 4 Output: False ``` Nodes `1`, `2` and `3` form a cycle reachable from node `0`, so the path `0 -> 1 -> 2 -> 3 -> 1 -> ...` never ends, even though node `4` is the only node without outgoing edges.

Overview: Given a directed graph, a source and a destination, decide whether every path that starts at the source eventually stops at the destination: no reachable dead end other than the destination and no reachable cycle. It tests graph traversal, cycle detection and precise reasoning about reachability.

Read the full ByteDance Software Engineer interview experience this question came from

You are given a directed graph with `n` nodes numbered `0` to `n - 1`, a list `edges` where `edges[i] = [u, v]` is a directed edge from node `u` to node `v`, and two nodes `source` and `destination`. Self-loops and repeated edges may appear. A path starts at `source` and keeps following outgoing edges. It ends only when it reaches a node that has no outgoing edges. Return `True` exactly when both of these hold, and `False` otherwise: 1. every node reachable from `source` that has no outgoing edges is `destination`; and 2. no path from `source` can continue forever: no cycle, including a self-loop, is reachable from `source`. `source` itself counts as reachable from `source`. If `source == destination` and that node has no outgoing edges, the answer is `True`. ### Example 1 ```text Input: n = 5, edges = [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]], source = 0, destination = 4 Output: True ``` Both paths, `0 -> 1 -> 3 -> 4` and `0 -> 2 -> 3 -> 4`, end at node `4`, which has no outgoing edges. ### Example 2 ```text Input: n = 5, edges = [[0, 1], [1, 2], [2, 3], [3, 1], [2, 4]], source = 0, destination = 4 Output: False ``` Nodes `1`, `2` and `3` form a cycle reachable from node `0`, so the path `0 -> 1 -> 2 -> 3 -> 1 -> ...` never ends, even though node `4` is the only node without outgoing edges. ### Constraints - `1 <= n <= 10^4` - `0 <= len(edges) <= 10^4` - For every edge `[u, v]`: `0 <= u, v < n`. Self-loops and repeated edges may appear. - `0 <= source, destination < n` (`source` may equal `destination`) - No value exceeds `2^31 - 1`, so a 32-bit `int` is sufficient in every language.

Constraints

  • 1 <= n <= 10^4
  • 0 <= len(edges) <= 10^4
  • For every edge [u, v]: 0 <= u, v < n; self-loops and repeated edges may appear
  • 0 <= source, destination < n (source may equal destination)
  • No value exceeds 2^31 - 1

Examples

Input: (5, [[0, 1], [0, 2], [1, 3], [2, 3], [3, 4]], 0, 4)

Expected Output: True

Explanation: Source example 1: diamond whose two branches meet at node 3 and end at destination 4; reaching node 3 twice is not a cycle.

Input: (4, [[0, 1], [0, 2], [2, 3]], 0, 3)

Expected Output: False

Explanation: Source example 2: the branch 0 -> 1 stops at sink 1, which is not destination 3.

Hints

  1. Only nodes reachable from `source` matter: a cycle or a dead end that `source` cannot reach does not change the answer, and `source` itself counts as reachable.
  2. There are two independent ways to fail: reaching a node with no outgoing edges that is not `destination`, or being able to keep walking forever around a cycle (a self-loop counts). For any path to stop at `destination`, it must have no outgoing edges.
  3. Reaching the same node along two different routes, as in a diamond, does not by itself form a cycle; make sure your check tells those two situations apart.

Loading coding console...

Show the approach

Approach

Algorithm: build adjacency lists from edges, then run an iterative depth-first search from source that keeps three states per node: unvisited, on the current path (still being explored), and fully explored. An explicit stack plus a per-node edge cursor replaces recursion, so a 10^4-node chain cannot hit a recursion limit.

Checks: when a node is first discovered (including source before the search starts), if it has no outgoing edges and is not destination, return False (rule 1). When an edge leads to a node that is on the current path, that edge closes a cycle reachable from source; a self-loop is the case where the edge leads back to the node itself. Return False (rule 2). An edge into a fully explored node is skipped: that node and everything it reaches were already checked.

Correctness: the search discovers exactly the nodes reachable from source, so every reachable node without outgoing edges is tested against destination. In a directed graph, a cycle is reachable from the start node exactly when depth-first search from it finds an edge into a node still on the current path (a back edge). Edges into fully explored nodes (cross or forward edges, such as a second route into a diamond's merge node or a repeated edge) never indicate a cycle. If the search finishes without returning False, neither rule is violated, so the answer is True.

Edge cases: n = 1 with no edges and source == destination is True; source with no outgoing edges is True only when it is destination; destination with any outgoing edge (including a self-loop) always yields False, because a path through it either continues to another dead end or cycles; cycles and dead ends that source cannot reach are never visited and do not affect the answer.

Time complexity:
O(n + len(edges))
Space complexity:
O(n + len(edges))