Friendship Network Reach
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".
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.
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.startUser within maxSteps, sorted in ascending order.u, v, startUser) will be valid and within the range 0 to n-1.[u, v] is in friendships, it means u is friends with v, and v is friends with u.maxSteps is 0, only the startUser should be returned.friendships is empty, only the startUser (if maxSteps >= 0) should be returned.Examples
Example 1
Input:
n = 5, friendships = [[0, 1], [1, 2], [2, 3]], startUser = 0, maxSteps = 1
Output:
[0, 1]
Note:
From user 0:
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:
Example 3
Input:
n = 4, friendships = [[0, 1], [2, 3]], startUser = 0, maxSteps = 3
Output:
[0, 1]
Note:
From user 0:
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
1 <= n <= 10000 <= friendships.length <= n * (n - 1) / 20 <= u, v < n, where u != v for any friendship [u, v].[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 < n0 <= maxSteps <= nmaxSteps and handles edge cases like maxSteps = 0 or disconnected graphs.friendships.Loading editor...