Nearest Favorite Cities
Google● MediumNEW GRADONSITE INTERVIEWProblem statement
An undirected, unweighted map contains n cities numbered from 0 to n - 1. Given the roads, a starting city, and a list of favorite cities, return every reachable favorite city whose shortest-path distance from the start is minimum.
Return the selected city IDs in increasing order. If no favorite city is reachable, return an empty array.
Function
nearestFavoriteCities(n: int, roads: int[][], start: int, favorites: int[]) → int[]Examples
Example 1
n = 6roads = [[0,1],[1,2],[0,3],[3,4],[4,5]]start = 0favorites = [2,4,5]return = [2,4]Cities two and four are both two roads away; city five is farther.
Example 2
n = 4roads = [[0,1],[1,2],[2,3]]start = 1favorites = [0,3]return = [0]City zero is one edge away, while city three is two edges away.
Example 3
n = 5roads = [[0,1],[2,3]]start = 0favorites = [3,4]return = []Neither favorite is reachable from city zero.
Constraints
1 <= n <= 200000.0 <= roads.length <= 300000.- Each road contains two distinct valid city IDs.
startand every favorite are valid city IDs.1 <= favorites.length <= n, and favorites are unique.