philosyang.com

1311. Get Watched Videos by Your Friends | 1653

You know it’s a graph question when you see the title. It’s a good BFS refresher, but I stumbled on sorting and it helped.

 1class Solution:
 2    def watchedVideosByFriends(
 3        self,
 4        watchedVideos: List[List[str]],
 5        friends: List[List[int]],
 6        id: int,
 7        level: int,
 8    ) -> List[str]:
 9        # use bfs to find friends list given level
10        dq = deque()
11        dq.append((id, 0))
12        seen = set([id])
13
14        while dq and dq[0][1] < level:
15            cur_id, cur_level = dq.popleft()
16            for friend in friends[cur_id]:
17                if friend not in seen:
18                    seen.add(friend)
19                    dq.append((friend, cur_level + 1))
20        # print(dq)
21
22        video_stats = []
23        while dq:
24            cur_id, cur_level = dq.popleft()
25            video_stats.extend(watchedVideos[cur_id])
26        video_cnt = Counter(video_stats)
27        # print(video_cnt)
28
29        sorted_result = sorted(video_cnt.items(), key=lambda x: (x[1], x[0]))
30        return [video for video, _ in sorted_result]

things to improve on:

  1. Level-order BFS: iterate by layers instead of storing (id, level) tuples. This avoids tracking levels per node and makes intent clear.
  2. Avoid the intermediate list: update the Counter directly from each friend’s videos.
  3. Drop unused vars: you don’t use cur_level when collecting videos.
  4. Tiny style nits: initialize deque with a list; use descriptive names.
 1class Solution:
 2    def watchedVideosByFriends(
 3        self,
 4        watchedVideos: List[List[str]],
 5        friends: List[List[int]],
 6        id: int,
 7        level: int,
 8    ) -> List[str]:
 9        # BFS to get exactly the friends at the given level
10        seen = {id}
11        q = deque([id])
12
13        for _ in range(level):
14            for _ in range(len(q)):          # iterate one "layer"
15                u = q.popleft()
16                for v in friends[u]:
17                    if v not in seen:
18                        seen.add(v)
19                        q.append(v)
20
21        # q now contains all friends at exactly 'level' distance
22        cnt = Counter()
23        for u in q:
24            cnt.update(watchedVideos[u])
25
26        # sort by (frequency asc, title asc) and return titles
27        return [title for title, _ in sorted(cnt.items(), key=lambda kv: (kv[1], kv[0]))]

takeaways:

  1. for loops for a specific level with bfs
  2. Counter.update()
  3. sorted(, key=lambda x)

This is a nice question!

#Array #Hashing #Breadth-First-Search #Graph #Sorting #Python