Skip to content

1311. Get Watched Videos by Your Friends 👎

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
 public:
  vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos,
                                        vector<vector<int>>& friends, int id,
                                        int level) {
    vector<string> ans;
    queue<int> q{{id}};
    vector<bool> seen(friends.size());
    seen[id] = true;
    unordered_map<string, int> count;
    set<pair<int, string>> freqAndVideo;

    for (int i = 0; i < level; ++i)
      for (int sz = q.size(); sz > 0; --sz) {
        for (const int friend_ : friends[q.front()])
          if (!seen[friend_]) {
            seen[friend_] = true;
            q.push(friend_);
          }
        q.pop();
      }

    for (int i = q.size(); i > 0; --i) {
      for (const string& video : watchedVideos[q.front()])
        ++count[video];
      q.pop();
    }

    for (const auto& [video, freq] : count)
      freqAndVideo.insert({freq, video});

    for (const auto& [_, video] : freqAndVideo)
      ans.push_back(video);

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
  public List<String> watchedVideosByFriends(List<List<String>> watchedVideos, int[][] friends,
                                             int id, int level) {
    Queue<Integer> q = new ArrayDeque<>(List.of(id));
    boolean[] seen = new boolean[friends.length];
    seen[id] = true;
    Map<String, Integer> count = new HashMap<>();

    for (int i = 0; i < level; ++i)
      for (int sz = q.size(); sz > 0; --sz) {
        for (final int friend : friends[q.peek()])
          if (!seen[friend]) {
            seen[friend] = true;
            q.offer(friend);
          }
        q.poll();
      }

    for (final int friend : q)
      for (final String video : watchedVideos.get(friend))
        count.merge(video, 1, Integer::sum);

    List<String> ans = new ArrayList<>(count.keySet());
    ans.sort((a, b)
                 -> count.get(a).equals(count.get(b)) ? a.compareTo(b)
                                                      : count.get(a).compareTo(count.get(b)));
    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
  def watchedVideosByFriends(
      self,
      watchedVideos: list[list[str]],
      friends: list[list[int]],
      id: int,
      level: int,
  ) -> list[str]:
    seen = [False] * 100
    seen[id] = True
    q = collections.deque([id])
    count = collections.Counter()

    for _ in range(level):
      for _ in range(len(q)):
        curr = q.popleft()
        for friend in friends[curr]:
          if not seen[friend]:
            seen[friend] = True
            q.append(friend)

    for friend in q:
      for video in watchedVideos[friend]:
        count[video] += 1

    return sorted(count, key=lambda video: (count[video], video))