Formatted question description: https://leetcode.ca/all/1311.html

# 1311. Get Watched Videos by Your Friends (Medium)

There are `n`

people, each person has a unique *id* between `0`

and `n-1`

. Given the arrays `watchedVideos`

and `friends`

, where `watchedVideos[i]`

and `friends[i]`

contain the list of watched videos and the list of friends respectively for the person with `id = i`

.

Level **1** of videos are all watched videos by your friends, level **2** of videos are all watched videos by the friends of your friends and so on. In general, the level `k`

of videos are all watched videos by people with the shortest path **exactly** equal to `k`

with you. Given your `id`

and the `level`

of videos, return the list of videos ordered by their frequencies (increasing). For videos with the same frequency order them alphabetically from least to greatest.

**Example 1:**

Input:watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 1Output:["B","C"]Explanation:You have id = 0 (green color in the figure) and your friends are (yellow color in the figure): Person with id = 1 -> watchedVideos = ["C"] Person with id = 2 -> watchedVideos = ["B","C"] The frequencies of watchedVideos by your friends are: B -> 1 C -> 2

**Example 2:**

Input:watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 2Output:["D"]Explanation:You have id = 0 (green color in the figure) and the only friend of your friends is the person with id = 3 (yellow color in the figure).

**Constraints:**

`n == watchedVideos.length == friends.length`

`2 <= n <= 100`

`1 <= watchedVideos[i].length <= 100`

`1 <= watchedVideos[i][j].length <= 8`

`0 <= friends[i].length < n`

`0 <= friends[i][j] < n`

`0 <= id < n`

`1 <= level < n`

- if
`friends[i]`

contains`j`

, then`friends[j]`

contains`i`

**Related Topics**:

Hash Table, String, Breadth-first Search

## Solution 1. BFS

```
// OJ: https://leetcode.com/problems/get-watched-videos-by-your-friends/
// Time: O(N + VlogV) where N is the number of people, and V is the count of the result videos
// Space: O(N)
class Solution {
public:
vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {
unordered_map<string, int> m;
queue<pair<int, int>> q;
vector<bool> seen(watchedVideos.size(), false);
q.emplace(id, 0);
seen[id] = true;
while (q.size()) {
auto [i, lv] = q.front();
q.pop();
if (lv == level) {
for (auto &v : watchedVideos[i]) m[v]++;
} else {
for (int nei : friends[i]) {
if (seen[nei]) continue;
seen[nei] = true;
if (seen[nei]) continue;
q.emplace(nei, lv + 1);
}
}
}
vector<string> ans;
for (auto &[v, cnt] : m) ans.push_back(v);
sort(begin(ans), end(ans), [&](string &a, string &b) { return m[a] != m[b] ? m[a] < m[b] : a < b; });
return ans;
}
};
```

Java

```
class Solution {
public List<String> watchedVideosByFriends(List<List<String>> watchedVideos, int[][] friends, int id, int level) {
int friendsCount = friends.length;
int[] colors = new int[friendsCount];
final int WHITE = 0;
final int GRAY = 1;
final int BLACK = 2;
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(id);
colors[id] = GRAY;
int friendLevel = 0;
while (!queue.isEmpty() && friendLevel < level) {
friendLevel++;
int size = queue.size();
for (int i = 0; i < size; i++) {
int curId = queue.poll();
int[] curFriends = friends[curId];
for (int friend : curFriends) {
if (colors[friend] == WHITE) {
colors[friend] = GRAY;
queue.offer(friend);
}
}
colors[curId] = BLACK;
}
}
Map<String, Integer> videosCountsMap = new HashMap<String, Integer>();
boolean flag = false;
while (!queue.isEmpty()) {
int curId = queue.poll();
List<String> curVideos = watchedVideos.get(curId);
for (String video : curVideos) {
int count = videosCountsMap.getOrDefault(video, 0);
count++;
videosCountsMap.put(video, count);
}
}
List<VideoFrequency> list = new ArrayList<VideoFrequency>();
Set<String> videosSet = videosCountsMap.keySet();
for (String video : videosSet) {
int count = videosCountsMap.get(video);
VideoFrequency videoFrequency = new VideoFrequency(video, count);
list.add(videoFrequency);
}
Collections.sort(list);
List<String> videos = new ArrayList<String>();
for (VideoFrequency videoFrequency : list)
videos.add(videoFrequency.video);
return videos;
}
}
class VideoFrequency implements Comparable<VideoFrequency> {
String video;
int frequency;
public VideoFrequency() {
}
public VideoFrequency(String video, int frequency) {
this.video = video;
this.frequency = frequency;
}
public int compareTo(VideoFrequency videoFrequency2) {
if (this.frequency != videoFrequency2.frequency)
return this.frequency - videoFrequency2.frequency;
else
return this.video.compareTo(videoFrequency2.video);
}
}
```