Exactly K Hops Away

MediumGraphs

Problem

A professional network has n members numbered 0 to n - 1 and mutual connections edges. A recruiter starting at member start wants to contact people who are neither too close nor too far.

Return, in increasing order, every member whose shortest connection distance from start is exactly k. Return an empty array if there are none.

Example 1

Input:
n = 6, edges = [[0,1],[0,2],[1,3],[2,3],[3,4],[4,5]], start = 0, k = 2
Output:
[3]

Member 3 is reachable in two hops through either 1 or 2. Member 4 is three hops away.

Example 2

Input:
n = 6, edges = [[0,1],[0,2],[1,3],[2,3],[3,4],[4,5]], start = 0, k = 0
Output:
[0]

Constraints

  • 1 ≤ n ≤ 10^5
  • 0 ≤ edges.length ≤ 2 · 10^5
  • 0 ≤ start < n
  • 0 ≤ k ≤ n

Hint

Show the first hint

Members at shortest distance k form one layer of a BFS.

Walkthrough

How to approach it

01Clarify before coding

  • Is it the shortest distance that must equal k, or any path of length k? The shortest distance.
  • What if k = 0? Return [start].
  • Must the output be sorted? Yes, ascending.

02Brute force

Enumerate all walks of length k from start with DFS and collect their endpoints, then remove those reachable by a shorter walk.

Cost: Exponential in k (branching factor to the power k), and the 'shorter walk' filter needs a BFS anyway.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.