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.

Learn more about Breadth-First Search, Graph and Sorting patterns.

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.

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.

Solution Implementation

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.

Learn more about how to find time and space complexity quickly using problem constraints.