#1311

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Get Watched Videos by Your Friends

Find videos watched by friends up to a given level and return them sorted by frequency and alphabetically.

array hash table breadth first search graph sorting

Problem Statement

In this problem, you are given two arrays: watchedVideos and friends. watchedVideos[i] is the list of videos watched by person i, and friends[i] is the list of friends for person i. You are also given a specific person’s id and a level, representing the number of hops away from the id that friends should be considered.

The task is to find the list of videos watched by the friends of the specified person up to the given level. The videos should be ordered by their frequency of appearance, in increasing order. If multiple videos have the same frequency, they should be ordered alphabetically.

Examples

Example 1

Input: watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 1

Output: ["B","C"]

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 = 2

Output: ["D"]

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

Solution Approach

Breadth-First Search (BFS)

Use BFS to find all friends at the specified level. Start from the given user's id, and explore their friends in levels. Collect the friends at the given level and gather the videos they have watched.

Count Video Frequencies

Once the relevant friends are found, count the frequency of each video they watched using a hash map. This allows us to efficiently track how often each video appears among the friends.

Sorting the Videos

Sort the collected videos first by their frequency, then alphabetically. This ensures that the output meets the problem's requirement of sorted videos.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n * m), where n is the number of people and m is the average number of videos watched by each person. BFS takes O(n) time, and counting frequencies and sorting the videos takes additional time proportional to the number of videos.

What Interviewers Usually Probe

Strong understanding of graph traversal algorithms like BFS is demonstrated.
Clear understanding of hash tables to track video frequencies.
Proper implementation of sorting with multiple criteria (frequency, then lexicographically).

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the BFS algorithm and incorrectly calculating the level of friends.
Failing to correctly count the frequency of videos watched by friends at the right level.
Not sorting the videos in both frequency order and lexicographically for ties.

Follow-up variants

Find videos watched by friends up to a different level (e.g., level 3).
Return the result sorted by different criteria, such as descending frequency.
Optimize the solution for larger inputs, handling the constraints more efficiently.

FAQ

How do I approach solving the "Get Watched Videos by Your Friends" problem?

Start by applying BFS to identify friends at the given level, then count the frequencies of their watched videos, and finally sort the results as required.

What data structures should I use for the "Get Watched Videos by Your Friends" problem?

Use a hash table to count video frequencies and a queue for BFS to track levels of friends.

What is the time complexity of the "Get Watched Videos by Your Friends" problem?

The time complexity is O(n * m), where n is the number of people and m is the average number of videos watched.

How does BFS help in solving the "Get Watched Videos by Your Friends" problem?

BFS helps find all friends up to the given level, ensuring you correctly explore the social network at the specified depth.

What are some common mistakes when solving the "Get Watched Videos by Your Friends" problem?

Common mistakes include miscalculating friend levels, failing to count video frequencies correctly, or sorting videos incorrectly.

terminal

Solution

Solution 1: BFS

We can use the Breadth-First Search (BFS) method to start from $\textit{id}$ and find all friends at a distance of $\textit{level}$, then count the videos watched by these friends.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class Solution:
    def watchedVideosByFriends(
        self,
        watchedVideos: List[List[str]],
        friends: List[List[int]],
        id: int,
        level: int,
    ) -> List[str]:
        q = deque([id])
        vis = {id}
        for _ in range(level):
            for _ in range(len(q)):
                i = q.popleft()
                for j in friends[i]:
                    if j not in vis:
                        vis.add(j)
                        q.append(j)
        cnt = Counter()
        for i in q:
            for v in watchedVideos[i]:
                cnt[v] += 1
        return sorted(cnt.keys(), key=lambda k: (cnt[k], k))

Continue Practicing

#1202 smallest string with swaps #928 minimize malware spread ii #924 minimize malware spread