Shortest Path in a Unit-Edge Graph
Amazon● MediumINTERNPHONE SCREENProblem statement
Given an undirected graph with vertices 0..n-1, distinct unit-weight edges, a start vertex, and a target vertex, return a shortest path from start to target as a vertex array including both endpoints.
If several paths use the minimum number of edges, return the lexicographically smallest vertex array. If no path exists, return an empty array. When start equals target, return the one-vertex path.
Function
shortestUnitPath(n: int, edges: int[][], start: int, target: int) → int[]Examples
Example 1
n = 5edges = [[0,2],[2,4],[0,1],[1,4],[1,3]]start = 0target = 4return = [0,1,4]Routes through 1 and 2 each have two edges; the route through 1 is lexicographically smaller.
Example 2
n = 4edges = [[0,1],[2,3]]start = 0target = 3return = []The target lies in a different connected component.
Example 3
n = 3edges = [[0,1],[1,2]]start = 1target = 1return = [1]No edge is needed when the start and target are the same vertex.
Constraints
1 <= n <= 2000 <= edges.length <= 2000- Every edge has two distinct endpoints in
0..n-1; no undirected edge is repeated. startandtargetare valid vertices.