We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Get Watched Videos by Your Friends

Difficulty: Medium

Problem Description

Given the arrays watchedVideos and friends, where watchedVideos[i] contains the list of watched videos and friends[i] contains the list of friends for the person with id = i. Level 1 of videos are all watched videos by your friends, level 2 are all watched videos by the friends of your friends, and so on. Given your id and the level of videos, return the list of videos ordered by their frequencies in increasing order. For videos with the same frequency, order them alphabetically.

Key Insights

  • The problem can be modeled as a graph where each person is a node, and edges exist between friends.
  • We can use Breadth-First Search (BFS) to traverse the graph and find the videos watched by friends at a specific level.
  • Counting the frequency of videos can be efficiently done using a hash table.
  • Sorting the result based on frequency and alphabetically is crucial for the final output.

Space and Time Complexity

Time Complexity: O(n + m log m), where n is the number of people and m is the number of videos watched at the specified level. Space Complexity: O(n + v), where n is the number of people and v is the number of unique videos watched.

Solution

To solve the problem, we will perform the following steps:

  1. Use BFS to explore the friends' graph up to the specified level.
  2. Collect watched videos from friends at that level into a hash table to count their frequencies.
  3. Sort the videos first by frequency and then alphabetically to produce the final result.

Code Solutions

from collections import deque, Counter

def watchedVideosByFriends(watchedVideos, friends, id, level):
    # BFS to find friends at the specified level
    queue = deque([id])
    visited = {id}
    current_level = 0
    
    while queue and current_level < level:
        for _ in range(len(queue)):
            person = queue.popleft()
            for friend in friends[person]:
                if friend not in visited:
                    visited.add(friend)
                    queue.append(friend)
        current_level += 1
    
    # Count the frequencies of watched videos of friends at the specified level
    video_count = Counter()
    while queue:
        person = queue.popleft()
        for video in watchedVideos[person]:
            video_count[video] += 1
    
    # Sort videos first by frequency, then alphabetically
    result = sorted(video_count.keys(), key=lambda x: (video_count[x], x))
    return result
← Back to All Questions