Shortest Path in an Unweighted Graph
Updated
Problem statement
You are given an undirected, unweighted graph with n vertices numbered from 0 through n - 1. Each pair edges[i] = [u, v] represents an edge connecting vertices u and v.
Given vertices source and target, return the minimum number of edges on any path from source to target. Return -1 if target is unreachable from source.
Function
shortestPathLength(n: int, edges: int[][], source: int, target: int) → intExamples
Example 1
n = 5edges = [[0,1],[1,2],[0,3],[3,4],[4,2]]source = 0target = 2return = 2The path 0 -> 1 -> 2 uses two edges, and no one-edge path connects 0 to 2.
Example 2
n = 4edges = [[0,1],[2,3]]source = 0target = 3return = -1Vertices 0 and 3 belong to different connected components.
Example 3
n = 3edges = [[0,1]]source = 2target = 2return = 0A vertex has distance 0 from itself.
Constraints
1 ≤ n ≤ 10^5.0 ≤ edges.length ≤ 2 * 10^5.- Each edge contains two distinct vertices in the range
[0, n - 1]. - No undirected edge appears more than once.
0 ≤ source, target < n.
More Citadel Online Assessment questions
- Possible MEX Values After One Optional IncrementOA · Seen Oct 2026
- Busy IntersectionOA · Seen Sep 2026
- Maximize Workday EarningsOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Minimum Changes for Palindromic BlocksOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Sep 2026
- Minimum Image Processing CostOA · Seen Jul 2026
- Process SchedulingOA · Seen Mar 2026
- Social Media SuggestionsOA · Seen May 2025
- Best Sum Downward Tree PathOA · Seen May 2025
- Price CheckOA · Seen Feb 2025
- Palindromic Substrings (LC 647 :)OA · Seen Jan 2025
Similar questions at other companies
- Distances to CyclesBelvedere Trading · OA
- Cogwheel Rotation DirectionsOpenAI · OAOpenAI interview questions
- Breadth-First Order of a GraphAdobe · PHONE SCREENAdobe interview questions
- Crawl Reachable Pages with Bounded RetriesSnowflake · PHONE SCREENSnowflake interview questions
- Connected GroupsVisa · OAVisa interview questions
- Visible Profiles CountIBM · OAIBM interview questions
- Count Connected Equal TilesIntuit · OAIntuit interview questions
- Directed Path ExistenceUnity · OA
- Lowest Common Ancestor with a Changing RootInfosys · OAInfosys interview questions
- Delivery Management SystemAkuna Capital · OAAkuna Capital interview questions
Citadel interview experiences
- Citadel Securities Quant Researcher Intern Loop: 1 Experience
- Citadel Securities Research Engineer Interview: 1 Experience
- Citadel Securities SWE Intern First Round: 2 Experiences
- Citadel Securities Experienced SWE Interviews: 1 Experience
- Citadel SWE Intern Later Rounds and Superday: 13 Experiences
- Citadel SWE Intern First-Round Questions: 20 Experiences