Problem Description

You have a social network with n people, where each person has a unique ID from 0 to n-1. You're given two arrays:

• watchedVideos[i]: list of videos watched by person with id = i
• friends[i]: list of friend IDs for person with id = i

The problem asks you to find videos watched by people at a specific "friendship distance" from you.

Understanding Friendship Levels:

• Level 1: Your direct friends
• Level 2: Friends of your friends (but not your direct friends)
• Level k: People exactly k steps away from you in the friendship network

Task: Given your id and a target level, you need to:

1. Find all people at exactly that friendship distance from you
2. Collect all videos watched by those people
3. Count how many times each video appears
4. Return the videos sorted by:
   • Frequency (ascending) - less frequent videos come first
   • If frequencies are equal, sort alphabetically (A to Z)

Example: If you're person 0 and want level 2 videos:

• First find all your direct friends (level 1)
• Then find their friends who aren't already in your visited set (level 2)
• Collect and count all videos watched by these level 2 friends
• Sort and return the result

The solution uses BFS to traverse the friendship graph level by level, ensuring we only collect videos from people at the exact specified distance.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

• Yes: The problem involves a social network where people (nodes) are connected through friendships (edges). We have friends[i] representing the adjacency list for person i.

Is it a tree?

• No: The friendship network is not a tree - it can have cycles (mutual friendships) and is undirected. A person can have multiple friends, and friendship paths can loop back.

Is the problem related to directed acyclic graphs?

• No: The friendship graph is undirected (if A is friends with B, then B is friends with A), and it can contain cycles.

Is the problem related to shortest paths?

• Yes: We need to find all people at exactly a specific distance (level) from the starting person. This is essentially finding all nodes at a specific shortest path distance.

Is the graph Weighted?

• No: All friendships have the same "weight" or distance of 1. Each friendship connection counts as one step in the path.

BFS

• Yes: Since we have an unweighted graph and need to find nodes at a specific distance, BFS is the appropriate algorithm.

Conclusion: The flowchart correctly leads us to use BFS (Breadth-First Search) for this problem. BFS is perfect here because:

1. It explores nodes level by level
2. It guarantees finding the shortest path in unweighted graphs
3. It allows us to stop exactly at the desired friendship level
4. It naturally groups all nodes at the same distance together

Intuition

The key insight is recognizing that this is a level-based graph traversal problem. When we think about "friendship distance," we're essentially asking: "Who can I reach by making exactly k friendship hops?"

Imagine standing in the center of concentric circles. Your immediate friends form the first circle around you. Their friends (who aren't already in previous circles) form the second circle, and so on. We want to collect videos from people standing in a specific circle.

Why BFS works perfectly here:

1. Level-by-level exploration: BFS naturally processes nodes in "waves" or levels. When we start from person id, BFS first visits all friends at distance 1, then all friends at distance 2, and so on.

2. Avoiding revisits: As we expand outward, we need to mark people as visited to avoid counting them multiple times. Someone might be friends with multiple people in our network, but we only want to reach them through the shortest path.

3. Exact distance control: Unlike DFS which might reach a person through a longer path first, BFS guarantees we reach everyone via their shortest path. By tracking how many levels we've traversed, we can stop exactly at the desired level.

The video counting part is straightforward once we identify the target people. We simply:

• Collect all videos watched by people at the target level
• Count frequencies using a hash map
• Sort by the given criteria (frequency first, then alphabetically)

The elegance of this solution lies in using BFS's natural property of level-wise traversal to precisely identify people at the exact friendship distance we need.

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

Solution Approach

The implementation follows the BFS pattern we identified, with careful attention to level control and video counting.

Step 1: Initialize BFS Setup

• Create a queue q with the starting person id
• Use a set vis to track visited people, initially containing just id
• These structures ensure we explore each person exactly once

Step 2: Level-wise Traversal We perform exactly level iterations to reach the target friendship distance:

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)

The outer loop runs level times, each iteration representing one friendship hop. The inner loop processes all people at the current level before moving to the next. This two-loop structure is crucial:

• The inner for _ in range(len(q)) ensures we process only the people at the current level
• We dequeue each person i and enqueue their unvisited friends j
• The vis set prevents cycles and repeated visits

Step 3: Count Videos at Target Level After level iterations, the queue contains exactly the people at distance level:

cnt = Counter()
for i in q:
    for v in watchedVideos[i]:
        cnt[v] += 1

We use Python's Counter to efficiently count video frequencies. For each person in the queue, we iterate through their watched videos and increment the count.

Step 4: Sort and Return Results

return sorted(cnt.keys(), key=lambda k: (cnt[k], k))

The sorting uses a custom key that creates tuples (frequency, video_name). Python's sort is stable and handles the two-tier sorting requirement:

• Primary sort by frequency (ascending)
• Secondary sort by video name (alphabetical) when frequencies match

Time Complexity: O(N + E) for BFS traversal where N is the number of people reached and E is the friendship connections explored, plus O(V log V) for sorting videos where V is the unique video count.

Space Complexity: O(N) for the queue and visited set, plus O(V) for the video counter.

Example Walkthrough

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

Setup:

• 4 people in the network (IDs: 0, 1, 2, 3)
• watchedVideos = [["A","B"], ["C"], ["B","C"], ["D"]]
• friends = [[1,2], [0,3], [0,3], [1,2]]
• We start from id = 0 and want videos at level = 2

Visualization of the friendship network:

    0 (watches: A,B)
   / \
  1   2 (watches: C) and (B,C)
   \ /
    3 (watches: D)

Step 1: Initialize BFS

• Queue: [0]
• Visited: {0}

Step 2: Level-wise Traversal

Level 1 iteration (finding direct friends):

• Process person 0 from queue
• Person 0's friends are [1, 2]
• Add unvisited friends to queue and mark as visited
• After Level 1: Queue = [1, 2], Visited = {0, 1, 2}

Level 2 iteration (finding friends of friends):

• Process person 1 from queue
  • Person 1's friends are [0, 3]
  • 0 is already visited, so only add 3
• Process person 2 from queue
  • Person 2's friends are [0, 3]
  • Both 0 and 3 are already visited (3 was just added)
• After Level 2: Queue = [3], Visited = {0, 1, 2, 3}

Step 3: Count Videos at Target Level

• Queue now contains people at exactly distance 2: [3]
• Person 3 watched videos: ["D"]
• Video count: {"D": 1}

Step 4: Sort and Return

• Only one video "D" with frequency 1
• Return: ["D"]

Let's trace through a more complex scenario where sorting matters:

Modified example: If person 3 had watched ["D", "A", "A", "B"] instead:

• Video count: {"D": 1, "A": 2, "B": 1}
• Sorting by (frequency, name):
  • ("B", 1) comes before ("D", 1) alphabetically
  • ("A", 2) has highest frequency
• Return: ["B", "D", "A"]

This example demonstrates how BFS naturally finds people at the exact friendship distance and how the two-tier sorting organizes the final video list.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n + m + v × log v)

The time complexity breaks down as follows:

• The BFS traversal visits each person at most once and explores each friendship edge at most once, taking O(n + m) time, where n is the number of people and m is the total number of friendship edges.
• After reaching the target level, we iterate through all friends at that level and count their watched videos, which takes O(v) time where v is the total number of videos watched by friends at the target level.
• The final sorting operation sorts the unique videos by their frequency and lexicographically, which takes O(v × log v) time in the worst case.
• Overall: O(n + m + v × log v)

Space Complexity: O(n + v)

The space complexity consists of:

• The vis set stores visited person IDs, which can contain at most n elements: O(n)
• The queue q stores person IDs and contains at most n elements at any point: O(n)
• The cnt Counter stores video frequencies, containing at most v unique videos: O(v)
• Overall: O(n + v)

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

Common Pitfalls

1. Processing Beyond the Target Level

One of the most common mistakes is accidentally including people from level k+1 when asked for level k. This happens when the BFS traversal isn't properly bounded.

Incorrect approach:

visited = {id}
queue = deque([id])
current_level = 0

while queue and current_level < level:
    current_level += 1
    for _ in range(len(queue)):
        person = queue.popleft()
        for friend in friends[person]:
            if friend not in visited:
                visited.add(friend)
                queue.append(friend)

# Bug: Queue might contain level k+1 people!
for person in queue:
    # This processes the wrong level
    process_videos(person)

Why it fails: After the last iteration, the queue contains people at level k+1, not level k.

Solution: Either track people at each level separately or ensure the queue contains exactly the target level after traversal completes (as shown in the correct implementation).

2. Including Already Visited People in Video Count

Another pitfall is forgetting to exclude the starting person or previously visited people from the target level, leading to incorrect video counts.

Incorrect approach:

# Missing visited set initialization
queue = deque([id])
for _ in range(level):
    new_level = []
    for person in queue:
        for friend in friends[person]:
            new_level.append(friend)  # No duplicate check!
    queue = deque(new_level)

Why it fails: If person A and person B are both friends with person C, person C gets added twice, doubling their video counts.

Solution: Always maintain a visited set and check membership before adding to the queue.

3. Incorrect Sorting Logic

The problem requires sorting by frequency first (ascending), then alphabetically. A common mistake is reversing this order or using descending frequency.

Incorrect approaches:

# Wrong: Alphabetical first, then frequency
return sorted(video_count.keys(), key=lambda v: (v, video_count[v]))

# Wrong: Descending frequency
return sorted(video_count.keys(), key=lambda v: (-video_count[v], v))

# Wrong: Not handling the secondary sort
return sorted(video_count.keys(), key=lambda v: video_count[v])

Solution: Use the correct tuple order in the sort key: (video_count[v], v) for ascending frequency, then alphabetical.

4. Edge Case: Level 0

When level = 0, the answer should be videos watched by the starting person themselves, not their friends.

Incorrect handling:

if level == 0:
    return []  # Wrong!

Correct handling:

# The main algorithm handles this correctly:
# After 0 iterations, queue still contains only [id]
# So we return videos watched by the starting person

5. Modifying the Queue During Iteration

Using the queue's current length dynamically can cause issues:

Incorrect approach:

for _ in range(level):
    # Bug: len(queue) changes during iteration!
    for i in range(len(queue)):
        if i >= len(queue):  # Might go out of bounds
            break
        person = queue.popleft()
        # ...

Solution: Capture the queue length before the inner loop starts: current_size = len(queue), then iterate exactly current_size times.