Frontend School

Friendship Network Reach

DSA
easy

Friendship Network Reach

Easy
Graph
BFS
DFS

Overview

In a social media platform like Sharechat, understanding the reach within a user's friendship network is crucial for various features, such as targeted content recommendations, community building, and identifying influential users. This problem challenges you to implement a core function that determines all unique users reachable from a starting user within a specified number of "friendship steps".

What you need to do / Task

You are tasked with writing a function that, given a total number of users, a list of bidirectional friendships, a starting user, and a maximum number of steps, returns all unique user IDs reachable from the startUser within maxSteps friendship connections. The result should be sorted in ascending order.

Input & output

Function Signature:

function findReachableUsers(n: number, friendships: number[][], startUser: number, maxSteps: number): number[]
  • n: An integer representing the total number of users in the network. Users are identified by IDs from 0 to n-1.
  • friendships: An array of [u, v] pairs, where each pair indicates a bidirectional friendship between user u and user v.
  • startUser: An integer representing the ID of the user from whom to start the reachability search.
  • maxSteps: An integer representing the maximum number of friendship steps (connections) allowed to reach other users. A maxSteps of 0 means only the startUser itself is considered reachable.
  • Returns: An array of unique user IDs (integers) that are reachable from startUser within maxSteps, sorted in ascending order.

Clarifications

  • All user IDs (u, v, startUser) will be valid and within the range 0 to n-1.
  • Friendships are always bidirectional. If [u, v] is in friendships, it means u is friends with v, and v is friends with u.
  • If maxSteps is 0, only the startUser should be returned.
  • If friendships is empty, only the startUser (if maxSteps >= 0) should be returned.

Examples

1

Example 1

Input:

n = 5, friendships = [[0, 1], [1, 2], [2, 3]], startUser = 0, maxSteps = 1

Output:

[0, 1]

Note:

From user 0:

  • Step 0: User 0
  • Step 1: User 1 (friend of 0) Users 2, 3 are beyond 1 step.
2

Example 2

Input:

n = 5, friendships = [[0, 1], [1, 2], [2, 3], [3, 4]], startUser = 0, maxSteps = 2

Output:

[0, 1, 2]

Note:

From user 0:

  • Step 0: User 0
  • Step 1: User 1 (friend of 0)
  • Step 2: User 2 (friend of 1) Users 3, 4 are beyond 2 steps.
3

Example 3

Input:

n = 4, friendships = [[0, 1], [2, 3]], startUser = 0, maxSteps = 3

Output:

[0, 1]

Note:

From user 0:

  • Step 0: User 0
  • Step 1: User 1 (friend of 0) Users 2 and 3 are in a separate component and not reachable from user 0.
4

Example 4

Input:

n = 3, friendships = [[0, 1], [1, 2]], startUser = 1, maxSteps = 0

Output:

[1]

Note:

With 0 maximum steps, only the start user itself is reachable.

Constraints

Constraints & assumptions

  • 1 <= n <= 1000
  • 0 <= friendships.length <= n * (n - 1) / 2
  • 0 <= u, v < n, where u != v for any friendship [u, v].
  • Friendship pairs [u, v] are unique (i.e., [0,1] and [1,0] will not both be present, nor will [0,1] appear multiple times).
  • 0 <= startUser < n
  • 0 <= maxSteps <= n

What interviewers evaluate

  • Correctness: The solution correctly identifies all unique users reachable within maxSteps and handles edge cases like maxSteps = 0 or disconnected graphs.
  • Algorithm Choice: Appropriate use of graph traversal (BFS is generally preferred for step-counting/shortest path in unweighted graphs).
  • Graph Representation: Efficient and correct construction of the graph from input friendships.
  • Time and Space Complexity: Understanding and discussing the implications of the chosen algorithm and data structures.
  • Code Quality: Readability, modularity, and clean handling of visited nodes and step counts.

Loading editor...