# Get Watched Videos by Your Friends **Difficulty:** MEDIUM [External](https://leetcode.com/problems/get-watched-videos-by-your-friends) Canonical: https://scaleengineer.com/dsa/problems/get-watched-videos-by-your-friends **Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search) **Data structures:** Array, Hash Table, Graph **Companies:** [Guidewire](https://scaleengineer.com/companies/guidewire) --- ## Problem 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:** **![](https://assets.glich.co/dsa/get-watched-videos-by-your-friends/image0.png)** **Input:** watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 1 **Output:** ["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:** **![](https://assets.glich.co/dsa/get-watched-videos-by-your-friends/image1.png)** **Input:** watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 2 **Output:** ["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` # Approaches ## BFS with Intermediate Sorting for Frequency Counting This approach first identifies the friends at the specified `level` using a Breadth-First Search (BFS). BFS is ideal for finding all nodes at a specific distance from a source node in an unweighted graph. After finding the target friends, it collects all their watched videos into a single list. To count frequencies, it first sorts this list of videos alphabetically. This groups identical videos together, making it easy to count them in a single pass. The resulting video-frequency pairs are then sorted again based on the problem's criteria (by frequency, then alphabetically). **Time:** O(N + E + V_total * log(V_total) + U * log(U)), where N is people, E is friendships, V_total is total videos watched by level-k friends, and U is unique videos. BFS is O(N + E). Sorting all videos is the bottleneck at O(V_total * log(V_total)). · **Space:** O(N + V_total), where N is the number of people and V_total is the total number of video instances. The BFS queue and visited array take O(N) space. The `allVideos` list takes O(V_total) space. **Pros:** Correctly solves the problem.; The BFS part is efficient for finding the friends. **Cons:** The frequency counting method is inefficient. Sorting the entire list of videos (`V_total`) can be slow if there are many videos and many friends.; Requires multiple passes over the video data and multiple sorting operations.; Uses more intermediate memory for the `allVideos` list compared to a map-based approach. ### Explanation The process is divided into two main phases: 1. **Finding Friends at `level`:** - A queue is initialized with the starting `id`. - A `visited` array or set is used to keep track of people already processed to avoid cycles and redundant computations. - The BFS proceeds in levels. We iterate `level` times. In each iteration, we process all the people currently in the queue (a single "level" of friends), and add their unvisited friends to the queue for the next level. - After `level` iterations, the people remaining in the queue are exactly at the shortest distance of `level` from the starting `id`. 2. **Collecting, Counting, and Sorting Videos:** - All videos watched by the friends found in the previous step are aggregated into one large list. - This list is sorted alphabetically. For example, `["C", "B", "C"]` becomes `["B", "C", "C"]`. - We then iterate through this sorted list to count the frequency of each unique video. We can do this by keeping track of the current video and a counter. When the video changes, we store the previous video and its count. - The list of (video, frequency) pairs is stored. - Finally, this list of pairs is sorted. The primary sorting key is the frequency (ascending), and the secondary key is the video name (alphabetical). - The sorted video names are extracted into the final result list. ```java import java.util.*; class Solution { public List getWatchedVideosByYourFriends(List> watchedVideos, int[][] friends, int id, int level) { // Step 1: BFS to find friends at the given level Queue queue = new LinkedList<>(); queue.offer(id); boolean[] visited = new boolean[friends.length]; visited[id] = true; int currentLevel = 0; while (!queue.isEmpty() && currentLevel < level) { int size = queue.size(); for (int i = 0; i < size; i++) { int person = queue.poll(); for (int friend : friends[person]) { if (!visited[friend]) { visited[friend] = true; queue.offer(friend); } } } currentLevel++; } // Step 2: Collect all videos from friends at the target level List allVideos = new ArrayList<>(); while (!queue.isEmpty()) { allVideos.addAll(watchedVideos.get(queue.poll())); } if (allVideos.isEmpty()) { return new ArrayList<>(); } // Step 3: Sort videos to count frequencies Collections.sort(allVideos); // Step 4: Count frequencies List> freqList = new ArrayList<>(); if (!allVideos.isEmpty()) { int count = 1; for (int i = 1; i < allVideos.size(); i++) { if (allVideos.get(i).equals(allVideos.get(i - 1))) { count++; } else { freqList.add(new AbstractMap.SimpleEntry<>(allVideos.get(i - 1), count)); count = 1; } } freqList.add(new AbstractMap.SimpleEntry<>(allVideos.get(allVideos.size() - 1), count)); } // Step 5: Sort by frequency, then by name Collections.sort(freqList, (a, b) -> { if (a.getValue().equals(b.getValue())) { return a.getKey().compareTo(b.getKey()); } return a.getValue() - b.getValue(); }); // Step 6: Extract sorted video names List result = new ArrayList<>(); for (Map.Entry entry : freqList) { result.add(entry.getKey()); } return result; } } ``` ### Algorithm - 1. Initialize a queue for BFS with `id` and a `visited` set containing `id`. - 2. Initialize `currentLevel = 0`. - 3. While the queue is not empty and `currentLevel < level`: - a. Get the size of the queue for the current level. - b. For `i` from 0 to size-1: - i. Dequeue a person `u`. - ii. For each friend `v` of `u`: - If `v` is not in `visited`: - Add `v` to `visited`. - Enqueue `v`. - c. Increment `currentLevel`. - 4. The people remaining in the queue are the friends at the target `level`. If the queue is empty, return an empty list. - 5. Create an empty list `allVideos`. - 6. For each person `p` in the queue, add all their watched videos to `allVideos`. - 7. Sort `allVideos` alphabetically. - 8. Create a list of pairs `videoFrequencies`. - 9. Iterate through the sorted `allVideos` to count frequencies and populate `videoFrequencies`. - 10. Sort `videoFrequencies` first by frequency (ascending) and then by video name (alphabetical). - 11. Extract the video names from the sorted `videoFrequencies` list and return it. ## Optimal BFS with Hash Map Frequency Counting This approach is the most efficient way to solve the problem. It also starts with a Breadth-First Search (BFS) to find the friends at the exact specified `level`. However, it improves upon the video processing part. Instead of collecting all videos into a list and sorting it, this method uses a Hash Map to count the frequencies of the videos in a single pass. This avoids the costly step of sorting all video occurrences. After counting, the map entries are converted to a list and sorted just once according to the problem's requirements. **Time:** O(N + E + V_total + U * log(U)), where N is people, E is friendships, V_total is total videos, and U is unique videos. BFS is O(N + E). Populating the map is O(V_total). Sorting unique videos is O(U * log(U)). This is faster as U <= V_total. · **Space:** O(N + U), where N is the number of people and U is the number of unique videos. The BFS structures take O(N) space. The frequency map and result list take O(U) space. **Pros:** Most efficient time complexity. The frequency counting is done in linear time with respect to the total number of videos.; Optimal space complexity, as it only stores unique videos in the map.; The logic is clean and follows standard patterns for graph traversal and frequency counting. **Cons:** No significant cons; this is the standard and best approach for this problem. ### Explanation The overall structure is similar to the first approach but with a more optimized second phase. 1. **Finding Friends at `level`:** - This part is identical to the first approach. A standard BFS is performed for `level` steps to find all people at the shortest distance of `level` from `id`. A queue and a `visited` set are used. 2. **Collecting, Counting, and Sorting Videos using a Hash Map:** - A Hash Map (`Map`) is created to store video frequencies. - We iterate through the list of friends at the target `level`. For each friend, we iterate through their list of watched videos. - For each video, we update its count in the hash map. `map.put(video, map.getOrDefault(video, 0) + 1)`. This single pass builds a complete frequency count of all relevant videos. - After populating the map, we extract its keys into a list. - This list is then sorted using a custom comparator that looks up frequencies in the map. The comparator first compares entries by frequency (ascending) and then by video name (alphabetical) for ties. - Finally, the sorted list of video names is returned. ```java import java.util.*; class Solution { public List getWatchedVideosByYourFriends(List> watchedVideos, int[][] friends, int id, int level) { // Step 1: BFS to find friends at the given level Queue queue = new LinkedList<>(); queue.offer(id); boolean[] visited = new boolean[friends.length]; visited[id] = true; int currentLevel = 0; while (!queue.isEmpty() && currentLevel < level) { int size = queue.size(); for (int i = 0; i < size; i++) { int person = queue.poll(); for (int friend : friends[person]) { if (!visited[friend]) { visited[friend] = true; queue.offer(friend); } } } currentLevel++; } // Step 2: Use a HashMap to count video frequencies Map freqMap = new HashMap<>(); while (!queue.isEmpty()) { int person = queue.poll(); for (String video : watchedVideos.get(person)) { freqMap.put(video, freqMap.getOrDefault(video, 0) + 1); } } // Step 3: Create a list of videos from the map keys List result = new ArrayList<>(freqMap.keySet()); // Step 4: Sort the list with a custom comparator Collections.sort(result, (a, b) -> { int freqA = freqMap.get(a); int freqB = freqMap.get(b); if (freqA != freqB) { return freqA - freqB; } return a.compareTo(b); }); return result; } } ``` ### Algorithm - 1. Initialize a queue for BFS with `id` and a `visited` set containing `id`. - 2. Initialize `currentLevel = 0`. - 3. While the queue is not empty and `currentLevel < level`: - a. Get the size of the queue for the current level. - b. For `i` from 0 to size-1: - i. Dequeue a person `u`. - ii. For each friend `v` of `u`: - If `v` is not in `visited`: - Add `v` to `visited`. - Enqueue `v`. - c. Increment `currentLevel`. - 4. The people remaining in the queue are the friends at the target `level`. - 5. Create an empty Hash Map `videoFrequencies` to store `(video, count)`. - 6. For each person `p` in the queue: - For each `video` in `watchedVideos[p]`: - Increment the count for `video` in the `videoFrequencies` map. - 7. Create a list from the entries of the `videoFrequencies` map. - 8. Sort this list using a custom comparator: first by frequency (ascending), then by video name (alphabetical). - 9. Create the final result list by adding the video names from the sorted list of entries. - 10. Return the result list. # Solutions ### Java ```java class Solution { public List watchedVideosByFriends(List> watchedVideos, int[][] friends, int id, int level) { int n = friends.length; boolean[] vis = new boolean[n]; Deque q = new LinkedList<>(); q.offerLast(id); vis[id] = true; while (level-- > 0) { for (int i = q.size(); i > 0; --i) { int u = q.pollFirst(); for (int v : friends[u]) { if (!vis[v]) { q.offerLast(v); vis[v] = true; } } } } Map freq = new HashMap<>(); while (!q.isEmpty()) { for (String w : watchedVideos.get(q.pollFirst())) { freq.put(w, freq.getOrDefault(w, 0) + 1); } } List> t = new ArrayList<>(freq.entrySet()); t.sort((a, b)->{ if (a.getValue() > b.getValue()) { return 1; } if (a.getValue() < b.getValue()) { return -1; } return a.getKey().compareTo(b.getKey()); }); List ans = new ArrayList<>(); for (Map.Entry e : t) { ans.add(e.getKey()); } return ans; } } ``` ### CPP ```cpp class Solution { public: vector watchedVideosByFriends(vector> &watchedVideos, vector> &friends, int id, int level) { queue q{{id}}; int n = friends.size(); vector vis(n); vis[id] = true; while (level--) { for (int k = q.size(); k; --k) { int i = q.front(); q.pop(); for (int j : friends[i]) { if (!vis[j]) { vis[j] = true; q.push(j); } } } } unordered_map cnt; while (!q.empty()) { int i = q.front(); q.pop(); for (const auto &v : watchedVideos[i]) { cnt[v]++; } } vector ans; for (const auto &[key, _] : cnt) { ans.push_back(key); } sort(ans.begin(), ans.end(), [&cnt](const string &a, const string &b) { return cnt[a] == cnt[b] ? a < b : cnt[a] < cnt[b]; }); return ans; } }; ``` ### Python ```python class Solution: def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int, ) -> List[str]: n = len(friends) vis = [False] * n q = deque([id]) vis[id] = True for _ in range(level): size = len(q) for _ in range(size): u = q . popleft() for v in friends[u]: if not vis[v]: q . append(v) vis[v] = True freq = Counter() for _ in range(len(q)): u = q . pop() for w in watchedVideos[u]: freq[w] += 1 videos = list(freq . items()) videos . sort(key=lambda x: (x[1], x[0])) return [v[0] for v in videos] ```