Shortest Distance in an Undirected Graph
Updated
Problem statement
An undirected, unweighted graph has n vertices numbered from 0 through n-1. Each row [a,b] in edges lets you move between a and b in either direction.
Return the smallest number of edges needed to travel from start to target. Return the distance only, not the route.
For this exercise, assume the distance is 0 when both vertices are the same and -1 when no route exists. Repeated edges, reversed copies, and self-loops are allowed; they do not shorten a route. Vertices absent from the edge list still exist.
Function
shortestDistance(n: int, edges: int[][], start: int, target: int) → intExamples
Example 1
n = 5edges = [[0,1],[1,2],[0,3],[3,4],[4,2]]start = 0target = 2return = 2The route 0 → 1 → 2 uses two edges. The other simple route, 0 → 3 → 4 → 2, uses three. There is no direct edge from 0 to 2, so the minimum is 2.
Example 2
n = 4edges = [[0,1],[2,3]]start = 0target = 3return = -1Vertices 0 and 1 form one component, while 2 and 3 form another. No route joins start 0 to target 3.
Constraints
- For this exercise, assume
1 <= n <= 200. 0 <= edges.length <= 2000.- Every edge contains exactly two integers, each from 0 through n-1.
0 <= start < nand0 <= target < n.
More Intuit Online Assessment questions
- Employee Promotion OpportunitiesOA · Seen Oct 2026
- Next Pascal Row CoefficientOA · Seen Oct 2026
- Parse Router LogsOA · Seen Oct 2026
- Longest Repeated Letter Block with Adjacent SwapsOA · Seen Oct 2026
- Maximum Square-Free DivisorOA · Seen Oct 2026
- Two Tribes from Taller-Person CountsOA · Seen Oct 2026
- Shortest Path from an Encoded GraphOA · Seen Sep 2026
- Oldest and Youngest EmployeesOA · Seen Sep 2026
- Pressure-Isolation Shutdown OrderOA · Seen Sep 2026
- Submask Sum QueriesOA · Seen Sep 2026
Similar questions at other companies
- Base Unit ConversionsAdobe · OAAdobe interview questions
- Delivery Management SystemAkuna Capital · OAAkuna Capital interview questions
- Minimize CommuteDatabricks · OA · PHONE SCREENDatabricks interview questions
- Tree Pythagorean TriplesIBM · OAIBM interview questions
- Shortest Atom Action PathOpenAI · OAOpenAI interview questions
- Distances to CyclesBelvedere Trading · OA
- Minimize Malware Spread by Removing a NodeVisa · OAVisa interview questions
- Longest Distance in a Frequency-Limited NetworkBloomberg LP · OABloomberg LP interview questions
- Minimum Cleaning Robot RunsHSBC · OAHSBC interview questions
- Find Minimum City HopsAmazon · OA