Get Watched Videos by Your Friends

medium graphs bfs hash table sorting

Problem

Each person i has a list of watchedVideos[i] and a list of friends[i]. Friendship is mutual. Level-k videos are those watched by all people whose shortest friendship-path distance from you is exactly k. Starting from your id, return the level-level videos ordered by frequency (increasing), breaking ties alphabetically.

InputwatchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 1

Output["B","C"]

Friends of 0 are 1 and 2. They watched C, B, C → B appears once, C twice. Sorted by frequency: B, C.

Inputid = 0, level = 2

Output["D"]

The only person two hops from 0 is person 3, who watched D.

watchedVideos (person|-separated, videos comma-separated)

friends (person|-separated, ids comma-separated)

id (start person)

level

def watchedVideosByFriends(watchedVideos, friends, id, level):
    seen = {id}
    frontier = [id]
    for _ in range(level):
        nxt = []
        for u in frontier:
            for v in friends[u]:
                if v not in seen:
                    seen.add(v)
                    nxt.append(v)
        frontier = nxt
    count = {}
    for u in frontier:
        for video in watchedVideos[u]:
            count[video] = count.get(video, 0) + 1
    return sorted(count, key=lambda v: (count[v], v))

function watchedVideosByFriends(watchedVideos, friends, id, level) {
  const seen = new Set([id]);
  let frontier = [id];
  for (let lvl = 0; lvl < level; lvl++) {
    const nxt = [];
    for (const u of frontier)
      for (const v of friends[u])
        if (!seen.has(v)) { seen.add(v); nxt.push(v); }
    frontier = nxt;
  }
  const count = new Map();
  for (const u of frontier)
    for (const video of watchedVideos[u])
      count.set(video, (count.get(video) || 0) + 1);
  return [...count.keys()].sort((a, b) =>
    count.get(a) - count.get(b) || (a < b ? -1 : 1));
}

List<String> watchedVideosByFriends(String[][] watchedVideos, int[][] friends, int id, int level) {
    Set<Integer> seen = new HashSet<>(); seen.add(id);
    List<Integer> frontier = new ArrayList<>(List.of(id));
    for (int lvl = 0; lvl < level; lvl++) {
        List<Integer> nxt = new ArrayList<>();
        for (int u : frontier)
            for (int v : friends[u])
                if (seen.add(v)) nxt.add(v);
        frontier = nxt;
    }
    Map<String, Integer> count = new HashMap<>();
    for (int u : frontier)
        for (String video : watchedVideos[u])
            count.merge(video, 1, Integer::sum);
    List<String> res = new ArrayList<>(count.keySet());
    res.sort((a, b) -> count.get(a).equals(count.get(b)) ? a.compareTo(b) : count.get(a) - count.get(b));
    return res;
}

vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {
    set<int> seen{id};
    vector<int> frontier{id};
    for (int lvl = 0; lvl < level; lvl++) {
        vector<int> nxt;
        for (int u : frontier)
            for (int v : friends[u])
                if (seen.insert(v).second) nxt.push_back(v);
        frontier = nxt;
    }
    map<string, int> count;
    for (int u : frontier)
        for (auto& video : watchedVideos[u]) count[video]++;
    vector<string> res;
    for (auto& p : count) res.push_back(p.first);
    sort(res.begin(), res.end(), [&](auto& a, auto& b) {
        return count[a] != count[b] ? count[a] < count[b] : a < b; });
    return res;
}

Explanation

The friendship lists form an undirected graph. "Shortest path exactly k" is the classic signal for a breadth-first search: BFS visits vertices in order of increasing distance, so after expanding level times the current frontier holds exactly the people at distance level from you.

We keep a seen set (so nobody is counted at two different distances) and a frontier list of the current layer. We start with just your id at distance 0. Each round, we gather every unseen neighbour of the current frontier into the next frontier and mark them seen. After level rounds, frontier is the target layer.

Marking people seen the moment they enter a layer is what enforces "exactly k": once someone is reached at the shortest distance, a longer path can never re-add them to a later layer.

With the target people known, we tally their watched videos into a count hash map. The answer is the set of distinct videos sorted by (frequency ascending, then name ascending) — a single comparator handles both keys.

BFS touches each vertex and edge once, and the final step sorts the distinct videos, giving an efficient overall solution.

Time: O(V + E + m log m) Space: O(V + m)