Quick Overview

Given a directed acyclic graph and two nodes, return the fewest edges on a directed path from the source to the target, 0 when they are the same node, or -1 when the target cannot be reached. Asked as a follow-up to topological ordering, it tests traversal of dependency graphs.

Fewest-Edge Distance Between Two Nodes in a Directed Acyclic Graph

Company: LinkedIn

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

This came as a follow-up to ordering the nodes of a dependency graph. You are given a directed acyclic graph with `n` nodes labeled `0` to `n - 1`, a list of directed edges where `[u, v]` is an edge from `u` to `v`, and two nodes `source` and `target`. Return the distance from `source` to `target`: the smallest number of edges on a path that starts at `source`, follows edges in their direction, and ends at `target`. ### Function Signature ```python def dag_distance(n: int, edges: list[list[int]], source: int, target: int) -> int: ``` ### Rules - An edge `[u, v]` can be followed only from `u` to `v`, never backwards. - If `source == target`, the distance is 0. - If no directed path from `source` to `target` exists, return `-1`. - An edge may be listed more than once; repeats do not change the answer. ### Constraints - `1 <= n <= 10^5` - `0 <= len(edges) <= 2 * 10^5` - `0 <= u, v, source, target < n` - the graph has no directed cycles and no self-loops ### Examples **Example 1** ```text Input: n = 6, edges = [[0, 1], [1, 2], [2, 5], [0, 3], [3, 5], [1, 4]], source = 0, target = 5 Output: 2 ``` The path `0 -> 3 -> 5` uses two edges; the other path, `0 -> 1 -> 2 -> 5`, uses three. **Example 2** ```text Input: n = 6, edges = [[0, 1], [1, 2], [2, 5], [0, 3], [3, 5], [1, 4]], source = 3, target = 2 Output: -1 ``` From node 3 the only edge leads to node 5, which has no outgoing edges, so node 2 cannot be reached. The edge `[1, 2]` cannot be used because node 1 is never reached from node 3. **Example 3** ```text Input: n = 3, edges = [[0, 1]], source = 2, target = 2 Output: 0 ``` The source is the target, so no edge is needed.

Overview: Given a directed acyclic graph and two nodes, return the fewest edges on a directed path from the source to the target, 0 when they are the same node, or -1 when the target cannot be reached. Asked as a follow-up to topological ordering, it tests traversal of dependency graphs.

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

You are given a directed acyclic graph with `n` nodes labeled `0` to `n - 1`, a list `edges` where each entry `[u, v]` is a directed edge from node `u` to node `v`, and two nodes `source` and `target`. Return the distance from `source` to `target`: the smallest number of edges on a path that starts at `source`, follows edges only in their direction, and ends at `target`. **Rules** - An edge `[u, v]` can be followed only from `u` to `v`, never backwards. - If `source == target`, the distance is `0`. - If no directed path from `source` to `target` exists, return `-1`. - An edge may be listed more than once; repeats do not change the answer. The answer is a single integer: either `-1` or a value in `[0, n - 1]`. It never exceeds 2^31 - 1, so a 32-bit `int` is enough in every language. **Example 1** ``` Input: n = 6, edges = [[0, 1], [1, 2], [2, 5], [0, 3], [3, 5], [1, 4]], source = 0, target = 5 Output: 2 ``` The path `0 -> 3 -> 5` uses two edges; the other path, `0 -> 1 -> 2 -> 5`, uses three. **Example 2** ``` Input: n = 6, edges = [[0, 1], [1, 2], [2, 5], [0, 3], [3, 5], [1, 4]], source = 3, target = 2 Output: -1 ``` From node 3 the only edge leads to node 5, which has no outgoing edges, so node 2 cannot be reached. The edge `[1, 2]` cannot be used because node 1 is never reached from node 3. **Constraints** - `1 <= n <= 10^5` - `0 <= len(edges) <= 2 * 10^5` - `0 <= u, v, source, target < n` - The graph has no directed cycles and no self-loops. - The same edge may appear more than once in `edges`.

Constraints

  • 1 <= n <= 10^5
  • 0 <= len(edges) <= 2 * 10^5
  • 0 <= u, v, source, target < n
  • The graph has no directed cycles and no self-loops
  • The same edge [u, v] may appear more than once in edges; repeats do not change the answer
  • The answer is -1 or an integer in [0, n - 1], so it fits in a 32-bit signed integer

Examples

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

Expected Output: 2

Explanation: Source example 1: 0 -> 3 -> 5 uses two edges, while the path listed first, 0 -> 1 -> 2 -> 5, uses three.

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

Expected Output: -1

Explanation: Source example 2: from 3 only node 5 is reachable; node 2 is reachable from ancestor 0 but not from 3.

Hints

  1. Edges are one-way. Only nodes you can reach from source by moving forward along edges can matter; an edge that starts somewhere you never reach is irrelevant.
  2. The order in which edges are listed is arbitrary and an edge may repeat. Make sure your answer cannot depend on either, and that the first path you happen to find is not mistaken for the shortest one.
  3. Decide the two special results up front: source == target gives 0, and a target that is never reached gives -1.

Loading coding console...

Show the approach

Approach

Build forward adjacency lists: each edge [u, v] is stored only under u, so it can never be followed backwards. Then run a breadth-first search from source. BFS removes nodes from its queue in nondecreasing order of distance, so the first time a node is discovered, the distance recorded for it (its parent's distance plus one) is the smallest number of edges on any directed path from source to that node. The search returns as soon as target is discovered. Edge cases: if source == target the answer is 0 before any edge is examined; if the queue empties without discovering target, no directed path exists and the answer is -1. A repeated edge only rediscovers a node that already has a distance, so it changes nothing. Only nodes reachable from source are visited, so edges elsewhere in the graph (for example a shortcut leaving an ancestor of source) cannot affect the result, and neither the order of the edges in the input nor the numbering of the nodes matters. Every node enters the queue at most once and every edge is scanned at most once. Because a shortest path visits distinct nodes, the answer is at most n - 1 and fits in a 32-bit int.

Time complexity:
O(n + m), where m = len(edges)
Space complexity:
O(n + m)