1311. Get Watched Videos by Your Friends


Problem Description

In this problem, you are given a social network of n people where each person is uniquely identified by an ID ranging from 0 to n-1. For each person, there is a list of watched videos and a list of friends. The goal is to find out what videos have been watched by people who are at an exact social distance of k from a given person (identified by his/her id), and list those videos in order of their popularity (i.e., how many times they've been watched), with ties broken alphabetically.

To elaborate:

  • Level 1 videos: Videos watched by your direct friends.
  • Level 2 videos: Videos watched by friends of your friends, and so on.
  • The 'level' indicates the social distance: if you are at level 0, level 1 is your direct friends, level 2 is friends of friends, and so on.

Your task is to determine the frequency of each video watched at the specified social distance (level 'k') from you and return the list of these videos sorted first by frequency, then alphabetically.

Intuition

To solve this problem, we use a technique known as Breadth-First Search (BFS), which is typically used for searching tree or graph data structures. It's a good fit here because the social network can be represented as a graph where nodes are people and edges are friendships.

Here's the step-by-step thought process:

  1. We start BFS from the given user's id to find all friends at distance k. This is achieved by running a loop for k iterations, where in each iteration, the search moves out one additional level of friendship.

  2. Throughout the BFS, we maintain a visited list to ensure we do not revisit the same person more than once.

  3. After completing the BFS, we have a list of people who are exactly k levels of friendship away from the given user. We then count the frequency of all videos watched by these people.

  4. Finally, we need to organize these videos. The problem requires us to sort the videos by their frequency in increasing order and break ties by sorting alphabetically. This sorted list is the desired output.

By using BFS, we ensure that we only look at the closest friends (smallest social distance) first before moving on to friends of friends and so on. The nature of BFS helps us solve the problem efficiently and orderly.

Solution Approach

The solution uses Breadth-First Search (BFS) to traverse the social network graph and a Counter (from Python's collections module) to tally the frequency of watched videos. The main steps of the solution approach are:

  1. Prepare BFS:

    • Begin by initializing a queue (here it's a deque for efficient pop and append operations) with the starting node, which is the person with the given ID.
    • Initialize a visited list vis with all entries set to False. This list keeps track of which nodes in the graph have already been visited so we don't process a node more than once.
  2. Execute BFS to Determine Friends at Level k:

    • Process nodes in the queue in batches corresponding to each level. For example, the first batch consists only of the starting node. The next batch will consist of all that node's friends, and so on.
    • For level iterations (the distance of friendship we're interested in):
      • Iterate over the number of elements (i.e., people) at the current level.
      • For each person at the current level, examine their friends and add them to the queue if they have not been visited yet.
  3. Aggregate Watched Videos by Level k Friends:

    • Initialize a freq Counter to keep track of how many times each video has been watched by friends at level k.
    • After BFS completes, process the remaining nodes in the queue (which are all at level k).
    • Count the frequency of each watched video using the Counter. This is done by iterating over each friend at level k and incrementally adding the counts of the videos they've watched.
  4. Sort the Results:

    • Finally, the videos need to be sorted first by frequency and then alphabetically. To do this:
      • Convert the freq Counter into a list of (video, count) pairs.
      • Sort this list by the count (frequency) in increasing order, and for counts that are the same, sort the videos alphabetically (the second part of the sorting key).
  5. Output the Sorted List:

    • After sorting, only the video names (the first element of each tuple in the sorted list) are returned as the final output in the required format.

The result is a list of video names that have been watched by people exactly k steps removed from the given user, sorted by the frequency with which they were watched, and alphabetically as a secondary sort criteria. This methodology ensures we meet the specifications of the problem statement precisely and efficiently.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's walk through an example to illustrate the solution approach.

Suppose we have a graph representing a social network of 4 people with the following friendships and videos watched:

IDs: [0, 1, 2, 3]

Friendship List:

  • Person 0 has friends [1, 2]
  • Person 1 has friends [0, 3]
  • Person 2 has friends [0, 3]
  • Person 3 has friends [1, 2]

Watched Videos:

  • Person 0: ["A", "B"]
  • Person 1: ["C"]
  • Person 2: ["B", "C"]
  • Person 3: ["A", "C"]

We want to find out which videos were watched by people at a social distance k = 2 from person 0. Based on the solution approach:

  1. Prepare BFS:

    • Initialize a queue with the starting node 0 and a visited list: [True, False, False, False] (as only person 0 is visited initially).
  2. Execute BFS to Determine Friends at Level k:

    • First level (friends of person 0): iterate over friends [1, 2]. Add these friends to the queue and mark them as visited. Queue: [1, 2], visited: [True, True, True, False].
    • Second level (person 0's friends' friends): iterate over friends of person 1 ([0, 3]) and friends of person 2 ([0, 3]). Only add person 3 to the queue as it has not been visited. Queue: [3], visited: [True, True, True, True].
  3. Aggregate Watched Videos by Level k Friends:

    • Initialize a freq Counter. After BFS, person 3 is left in the queue, who is exactly k = 2 levels away from person 0.
    • Count the frequency of each video watched by person 3: Counter({"A": 1, "C": 1}).
  4. Sort the Results:

    • Convert the Counter to a list of (video, count) pairs: [("A", 1), ("C", 1)].
    • Sort the list by count and alphabetically: the list stays [("A", 1), ("C", 1)] as the counts are the same and they are already in alphabetical order.
  5. Output the Sorted List:

    • Extract and return the sorted list of video names: ["A", "C"].

The final output is ["A", "C"], representing the videos watched by people exactly 2 social levels away from person 0, sorted by popularity and then alphabetically.

Python Solution

1from collections import deque, Counter
2from typing import List
3
4class Solution:
5    def watchedVideosByFriends(
6        self,
7        watched_videos: List[List[str]],
8        friend_connections: List[List[int]],
9        user_id: int,
10        friend_level: int,
11    ) -> List[str]:
12        # Number of users in the friend network
13        num_users = len(friend_connections)
14        # Boolean list to track visited users
15        visited = [False] * num_users
16        # Initialize the queue with the start user_id
17        que = deque([user_id])
18        # Mark the start user as visited
19        visited[user_id] = True
20      
21        # Traverse through the network to reach the specified friend level
22        for _ in range(friend_level):
23            level_size = len(que)
24            for _ in range(level_size):
25                current_user = que.popleft()
26                # Add unvisited friends of the current user to the queue
27                for friend_id in friend_connections[current_user]:
28                    if not visited[friend_id]:
29                        que.append(friend_id)
30                        visited[friend_id] = True
31      
32        # Counter to keep frequency of watched video titles
33        video_freq = Counter()
34        # Traverse through friends at specified level to count the videos watched
35        while que:
36            current_user = que.pop()
37            for video in watched_videos[current_user]:
38                video_freq[video] += 1
39      
40        # Convert the counter to a list of tuples and sort by frequency and lexicographical order
41        sorted_videos = sorted(video_freq.items(), key=lambda x: (x[1], x[0]))
42      
43        # Return just the video titles, discarding the frequency
44        return [video[0] for video in sorted_videos]
45

Java Solution

1import java.util.*;
2
3class Solution {
4    public List<String> watchedVideosByFriends(
5        List<List<String>> watchedVideos, int[][] friends, int id, int level) {
6      
7        int totalFriends = friends.length; // Total number of friends.
8        boolean[] visited = new boolean[totalFriends]; // Keep track of visited friends.
9        Queue<Integer> queue = new LinkedList<>(); // Queue for BFS (Breadth-First Search).
10        queue.offer(id); // Starting with the given friend's ID.
11        visited[id] = true;
12      
13        // Perform BFS to reach the friends at the specified level.
14        while (level-- > 0) {
15            int size = queue.size();
16            for (int i = 0; i < size; ++i) {
17                int currentFriend = queue.poll();
18                // Enqueue all unvisited friends of the current friend.
19                for (int friendId : friends[currentFriend]) {
20                    if (!visited[friendId]) {
21                        queue.offer(friendId);
22                        visited[friendId] = true;
23                    }
24                }
25            }
26        }
27      
28        // Count the frequency of each video watched by friends at the given level.
29        Map<String, Integer> frequencyMap = new HashMap<>();
30        while (!queue.isEmpty()) {
31            int friendAtLevel = queue.poll();
32            for (String video : watchedVideos.get(friendAtLevel)) {
33                frequencyMap.put(video, frequencyMap.getOrDefault(video, 0) + 1);
34            }
35        }
36      
37        // Convert the frequency map to a list, to sort them.
38        List<Map.Entry<String, Integer>> frequencyList = new ArrayList<>(frequencyMap.entrySet());
39        frequencyList.sort((entry1, entry2) -> {
40            if (!entry1.getValue().equals(entry2.getValue())) {
41                return entry1.getValue().compareTo(entry2.getValue());
42            }
43            // If frequencies are equal, sort alphabetically.
44            return entry1.getKey().compareTo(entry2.getKey());
45        });
46      
47        // Extract the sorted video names.
48        List<String> result = new ArrayList<>();
49        for (Map.Entry<String, Integer> entry : frequencyList) {
50            result.add(entry.getKey());
51        }
52      
53        return result; // Final sorted list of videos.
54    }
55}
56

C++ Solution

1#include <vector>
2#include <string>
3#include <unordered_map>
4#include <unordered_set>
5#include <queue>
6#include <algorithm>
7
8using namespace std;
9
10class Solution {
11public:
12    vector<string> watchedVideosByFriends(
13        vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {
14      
15        int totalFriends = friends.size(); // Total number of friends.
16        vector<bool> visited(totalFriends, false); // Keep track of visited friends.
17        queue<int> queue; // Queue for BFS (Breadth-First Search).
18        queue.push(id); // Starting with the given friend's ID.
19        visited[id] = true;
20      
21        // Perform BFS to reach the friends at the specified level.
22        while (level-- > 0) {
23            int size = queue.size();
24            for (int i = 0; i < size; ++i) {
25                int currentFriend = queue.front();
26                queue.pop();
27                // Enqueue all unvisited friends of the current friend.
28                for (int friendId : friends[currentFriend]) {
29                    if (!visited[friendId]) {
30                        queue.push(friendId);
31                        visited[friendId] = true;
32                    }
33                }
34            }
35        }
36      
37        // Count the frequency of each video watched by friends at the given level.
38        unordered_map<string, int> frequencyMap;
39        while (!queue.empty()) {
40            int friendAtLevel = queue.front();
41            queue.pop();
42            for (string& video : watchedVideos[friendAtLevel]) {
43                frequencyMap[video]++;
44            }
45        }
46      
47        // Convert the frequency map to a list, to sort them.
48        vector<pair<string, int>> frequencyList(frequencyMap.begin(), frequencyMap.end());
49        sort(frequencyList.begin(), frequencyList.end(), 
50             [](const pair<string, int>& entry1, const pair<string, int>& entry2) {
51                 // If frequencies are different, sort by frequency.
52                 if (entry1.second != entry2.second) {
53                     return entry1.second < entry2.second;
54                 }
55                 // If frequencies are equal, sort alphabetically.
56                 return entry1.first < entry2.first;
57             });
58      
59        // Extract the sorted video names.
60        vector<string> result;
61        for (auto& entry : frequencyList) {
62            result.push_back(entry.first);
63        }
64      
65        return result; // Final sorted list of videos.
66    }
67};
68

Typescript Solution

1import { PriorityQueue } from '@datastructures-js/priority-queue';
2
3// This function takes a list of lists containing videos watched, a 2D array
4// of friend relationships, the id of the user in question, and a level, and
5// returns a list of videos watched by friends on that level, sorted by frequency
6// and then alphabetically.
7function watchedVideosByFriends(
8    watchedVideos: string[][], 
9    friends: number[][], 
10    id: number, 
11    level: number
12): string[] {
13
14    const totalFriends = friends.length; // Total number of friends
15    const visited = new Array(totalFriends).fill(false); // Keep track of visited friends
16    const queue: number[] = []; // Queue for BFS (Breadth-First Search)
17  
18    // Start with the given friend's ID
19    queue.push(id);
20    visited[id] = true;
21  
22    // Perform BFS to reach the friends at the specified level
23    while (level > 0) {
24        let size = queue.length;
25        for (let i = 0; i < size; ++i) {
26            const currentFriend = queue.shift()!; // The non-null assertion is for TypeScript
27
28            // Enqueue all unvisited friends of the current friend
29            for (let friendId of friends[currentFriend]) {
30                if (!visited[friendId]) {
31                    queue.push(friendId);
32                    visited[friendId] = true;
33                }
34            }
35        }
36        level -= 1; // Decrement level after finishing a BFS level
37    }
38  
39    // Count the frequency of each video watched by friends at the given level
40    const frequencyMap: Record<string, number> = {};
41    while (queue.length > 0) {
42        const friendAtLevel = queue.shift()!;
43        for (let video of watchedVideos[friendAtLevel]) {
44            frequencyMap[video] = (frequencyMap[video] || 0) + 1;
45        }
46    }
47  
48    // Convert the frequency map to a list, sorted by frequency and then alphabetically
49    const sortedVideos: string[] = Object.keys(frequencyMap)
50        .sort((a, b) => {
51            if (frequencyMap[a] !== frequencyMap[b]) {
52                return frequencyMap[a] - frequencyMap[b];
53            }
54            return a.localeCompare(b);
55        });
56  
57    // Return the sorted list of video names
58    return sortedVideos;
59}
60
61// Define a type for the input parameters of watchedVideosByFriends function
62type FriendVideoWatchlist = {
63    watchedVideos: string[][],
64    friends: number[][],
65    id: number,
66    level: number
67};
68
69export { watchedVideosByFriends, FriendVideoWatchlist };
70

Time and Space Complexity

Time Complexity

The time complexity of the code involves several parts:

  1. BFS Traversal: We are using a Breadth-First Search (BFS) algorithm to find all friends at the given level. BFS has a time complexity of O(V + E), where V is the number of vertices (or friends, in this context) and E is the number of edges (or friendships). In the worst case, the BFS could potentially visit all n vertices and all connections between friends, so this part of the code is O(n + E).

  2. Counting Frequency: After BFS, the code counts the frequency of each video watched by friends at the given level. Assuming the number of friends at that level is F and each friend has watched at most W videos, the time complexity for counting frequency would be O(FW) because we iterate through each friend and update the counter for every video they have watched.

  3. Sorting Videos: Next, the algorithm sorts the videos by frequency and by their names if frequencies are equal using a custom sorting function. Assuming there are V distinct videos, the sorting takes O(V * log(V)) time because sorting algorithms generally have an O(n * log(n)) complexity where n is the number of items to sort.

Therefore, the overall time complexity of the code is O(n + E + FW + V * log(V)). However, considering that E, FW, and V are all limited by n (since E <= n(n-1)/2, FW <= nW, and V <= nW), we can simplify the time complexity to O(n^2 + nW + nW * log(nW)).

Space Complexity

The space complexity is determined by the additional space required for the BFS queue, the visitation list, and the counters for the videos:

  1. Visitation List: The vis list keeps track of whether a friend has been visited during BFS. It contains one entry per friend, so its space complexity is O(n).

  2. BFS Queue: In the worst case, the BFS queue can have up to n elements (if every friend is at the required level), so its space complexity is O(n).

  3. Counters for Videos: The Counter for videos and the list of videos after conversion (freq and videos) can store at most FW elements, which is O(FW). In the worst case, the space complexity for counting videos is equal to the total number of videos watched by all friends, which is O(n * W) if each person has watched at most W videos.

Hence, the overall space complexity is O(n + n + n * W) which can be simplified to O(nW) since W >= 1.

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫