Shortest Path in an Unweighted Graph
Updated
Problem statement
You are given a connected graph with vertices numbered from 1 through n. Its edges are undirected and unweighted, with no self-loops or repeated edges. Return a shortest path from source to target. Each pair in edges is one undirected edge.
For this exercise, assume paths are returned as arrays of vertex labels including both endpoints. Choose a path with the fewest edges. If several paths tie, return the lexicographically smallest sequence of vertex labels: compare them from the start and choose the one with the smaller label at the first difference. If both endpoints are the same, return that single vertex.
Function
shortestUnweightedPath(n: int, edges: int[][], source: int, target: int) → int[]Examples
Example 1
n = 5edges = [[1,3],[3,4],[1,2],[2,4],[4,5]]source = 1target = 5return = [1,2,4,5]Both routes through 2 and 3 have three edges. The path through 2 is lexicographically smaller.
Example 2
n = 3edges = [[1,2],[2,3]]source = 2target = 2return = [2]A vertex reaches itself using zero edges.
Constraints
- For this exercise, assume
1 <= n <= 1000. - The graph is connected and has at most
10000edges, with no self-loop or repeated undirected edge. - Every edge endpoint, source and target is an integer in
[1,n].
More PeopleStrong interview questions
- Reverse Linked-List Nodes in Groups of KOA · PHONE SCREEN · Seen Mar 2026
- Unique Paths Through a GridOA · Seen Mar 2026
- Aggressive CowsOA · Seen Oct 2021
- Total Set Bits from 1 to NOA · Seen Oct 2021
- Swap Two Array ElementsOA · Seen Sep 2021
- Minimum Travel Time with Flashing Traffic LightsOA · Seen Aug 2021
- Permutation in a StringOA · Seen Aug 2021
- Rat in a Maze: All Simple PathsOA · Seen Aug 2021
- Add Two Binary StringsONSITE INTERVIEW · Seen Mar 2026
- Four SumONSITE INTERVIEW · Seen Mar 2026
Similar questions at other companies
- Delivery Management SystemAkuna Capital · OAAkuna Capital interview questions
- Shortest Path from an Encoded GraphIntuit · OAIntuit interview questions
- Longest Distance in a Frequency-Limited NetworkBloomberg LP · OABloomberg LP interview questions
- Find Minimum City HopsAmazon · OA
- Grid ExplorationIMC Trading · OAIMC Trading interview questions
- Shortest Route Through a Traced MazeDuolingo · OADuolingo interview questions
- Drone Delivery with Battery Swap StationsCisco · OACisco interview questions
- Fire Station Response BillLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Shortest Word Chain Between Two WordsFanatics · PHONE SCREEN
- Shortest Path Node Count Avoiding Broken NodesGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions