LeetCode 1311 - Get Watched Videos by Your Friends

LeetCode Problem 1311

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Breadth-First Search, Graph Theory, Sorting

Solution

Problem Understanding

This problem models a social network as an undirected graph. Each person is represented by an integer ID from 0 to n - 1. The friends array describes the graph connections, while watchedVideos[i] contains the list of videos watched by person i.

The goal is to find all videos watched by people who are exactly a certain friendship distance away from a starting person.

A friendship distance is defined using the shortest path in the graph:

• Distance 1 means direct friends
• Distance 2 means friends of friends
• Distance k means all people whose shortest path from the starting person is exactly k

After identifying all people at the target level, we collect every video they watched and count frequencies. The final result must be sorted:

1. By frequency in ascending order
2. If frequencies are equal, alphabetically in ascending order

The graph is guaranteed to be undirected because if friends[i] contains j, then friends[j] also contains i.

The constraints are relatively small:

• n <= 100
• Each person can watch up to 100 videos

These limits strongly suggest that a graph traversal solution such as Breadth First Search is appropriate and efficient enough.

Several edge cases are important:

• Multiple people at the same level may watch the same video
• Videos with equal frequency must be sorted alphabetically
• Cycles exist in the friendship graph, so revisiting nodes must be prevented
• Only people at the exact target level should contribute videos
• The starting person should never be counted unless reachable again through a longer path, which BFS naturally prevents through visitation tracking

Approaches

Brute Force Approach

A brute force solution would attempt to compute distances between the starting person and every other person individually.

One possible method is:

1. For every person in the graph:

• Run a search to determine the shortest distance from id

2. Collect people whose distance equals level
3. Count all their watched videos
4. Sort the result according to the problem rules

This approach is correct because shortest path computation guarantees we identify exactly the desired friendship level.

However, it is inefficient because we repeatedly traverse the graph for each person. If we run BFS from the source separately for every target node, the work becomes unnecessarily duplicated.

Since the graph is unweighted, a single BFS from the starting node already computes shortest distances to all nodes simultaneously.

Optimal Approach

The key observation is that Breadth First Search naturally explores an unweighted graph level by level.

When BFS starts from the given id:

• The first BFS layer contains all nodes at distance 1
• The second BFS layer contains all nodes at distance 2
• And so on

Therefore, after exactly level BFS expansions, the queue contains precisely the people whose shortest path distance equals the target level.

Once these people are identified:

1. Count their watched videos using a hash map
2. Sort videos by:

• Frequency ascending
• Lexicographical order ascending

This avoids repeated shortest path computations and processes the graph efficiently in one traversal.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × (n + e))	O(n)	Runs graph traversal repeatedly for multiple nodes
Optimal	O(n + e + v log v)	O(n + v)	Single BFS traversal, then sort unique videos

Here:

• n = number of people
• e = number of friendship edges
• v = number of unique videos collected at the target level

Algorithm Walkthrough

1. Initialize a queue for BFS and place the starting person id inside it.

BFS is ideal because it explores nodes in increasing order of shortest path distance. 2. Maintain a visited set.

Since the friendship graph may contain cycles, we must avoid revisiting people repeatedly. 3. Perform BFS level by level until reaching the target distance.

For each BFS layer:

• Process all nodes currently in the queue
• Add their unvisited friends into the queue
• Mark newly discovered friends as visited

After processing one layer, all nodes in the queue belong to the next friendship level. 4. After exactly level expansions, the queue contains all people at the desired distance.

These are the only people whose watched videos should be counted. 5. Create a frequency map for videos.

Iterate through every person remaining in the queue:

• For each watched video:

• Increment its count in the hash map

6. Sort the videos.

The sorting criteria are:

• Lower frequency first
• Alphabetically smaller name first when frequencies tie

In Python, this can be done with:

sorted(freq.keys(), key=lambda x: (freq[x], x))

7. Return the sorted list of video names.

Why it works

Breadth First Search guarantees that nodes are explored in increasing order of shortest path distance from the starting node. Therefore, after processing exactly level BFS layers, the remaining nodes in the queue are exactly the people whose shortest distance from id equals level.

Since we count videos only from those people, and then sort according to the required rules, the algorithm always produces the correct output.

Python Solution

from collections import deque, defaultdict
from typing import List

class Solution:
    def watchedVideosByFriends(
        self,
        watchedVideos: List[List[str]],
        friends: List[List[int]],
        id: int,
        level: int
    ) -> List[str]:

        queue = deque([id])
        visited = set([id])

        current_level = 0

        while queue and current_level < level:
            level_size = len(queue)

            for _ in range(level_size):
                person = queue.popleft()

                for friend in friends[person]:
                    if friend not in visited:
                        visited.add(friend)
                        queue.append(friend)

            current_level += 1

        frequency = defaultdict(int)

        for person in queue:
            for video in watchedVideos[person]:
                frequency[video] += 1

        return sorted(frequency.keys(), key=lambda video: (frequency[video], video))

The implementation begins by initializing a BFS queue with the starting person. A visited set prevents revisiting people and getting trapped in graph cycles.

The BFS loop runs until the desired friendship level is reached. Each iteration processes exactly one BFS layer. This is done using level_size, which captures how many nodes belong to the current distance level.

Once BFS finishes, the queue contains only people at the target level. Their watched videos are counted using a defaultdict(int) frequency map.

Finally, the result is sorted using the problem's required ordering. The tuple (frequency[video], video) ensures frequency takes priority, while alphabetical order resolves ties.

Go Solution

package main

import (
	"sort"
)

func watchedVideosByFriends(
	watchedVideos [][]string,
	friends [][]int,
	id int,
	level int,
) []string {

	queue := []int{id}
	visited := make(map[int]bool)
	visited[id] = true

	currentLevel := 0

	for len(queue) > 0 && currentLevel < level {
		levelSize := len(queue)
		nextQueue := []int{}

		for i := 0; i < levelSize; i++ {
			person := queue[i]

			for _, friend := range friends[person] {
				if !visited[friend] {
					visited[friend] = true
					nextQueue = append(nextQueue, friend)
				}
			}
		}

		queue = nextQueue
		currentLevel++
	}

	frequency := make(map[string]int)

	for _, person := range queue {
		for _, video := range watchedVideos[person] {
			frequency[video]++
		}
	}

	result := []string{}

	for video := range frequency {
		result = append(result, video)
	}

	sort.Slice(result, func(i, j int) bool {
		if frequency[result[i]] == frequency[result[j]] {
			return result[i] < result[j]
		}
		return frequency[result[i]] < frequency[result[j]]
	})

	return result
}

The Go solution follows the same BFS strategy as the Python version.

One notable difference is queue management. Instead of using a dedicated deque structure, the implementation creates a nextQueue slice for the next BFS layer.

The frequency map uses map[string]int, which automatically defaults missing keys to 0.

Sorting is handled using sort.Slice, where the comparator implements the required two level ordering:

1. Frequency ascending
2. Alphabetical order ascending

Go slices naturally represent dynamic arrays, making them suitable for both BFS queues and the final result list.

Worked Examples

Example 1

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

The friendship graph is:

0 -> 1, 2
1 -> 0, 3
2 -> 0, 3
3 -> 1, 2

BFS Traversal

Step	Queue	Visited	Current Level
Initial	[0]	{0}	0

Process node 0:

• Discover friend 1
• Discover friend 2

Step	Queue	Visited	Current Level
After Level 1	[1, 2]	{0,1,2}	1

We stop because we reached the target level.

Count Videos

Person 1 watched:

["C"]

Person 2 watched:

["B", "C"]

Frequency map:

Video	Frequency
B	1
C	2

Sorting

Sorted by frequency ascending:

["B", "C"]

Example 2

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

BFS Traversal

Step	Queue	Visited	Current Level
Initial	[0]	{0}	0

After processing level 1:

Step	Queue	Visited	Current Level
Level 1	[1,2]	{0,1,2}	1

Process nodes 1 and 2:

• Both connect to 3
• 3 added once because of visited tracking

Step	Queue	Visited	Current Level
Level 2	[3]	{0,1,2,3}	2

We stop because target level reached.

Count Videos

Person 3 watched:

["D"]

Frequency map:

Video	Frequency
D	1

Result:

["D"]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + e + v log v)	BFS traverses graph once, sorting unique videos costs v log v
Space	O(n + v)	Visited set, queue, and frequency map

The BFS traversal processes every person and friendship edge at most once. Video counting processes only people at the target level. The final sorting step dominates when many distinct videos exist.

Since the constraints are small, this solution easily fits within time limits.

Test Cases

from typing import List

class Solution:
    def watchedVideosByFriends(
        self,
        watchedVideos: List[List[str]],
        friends: List[List[int]],
        id: int,
        level: int
    ) -> List[str]:

        from collections import deque, defaultdict

        queue = deque([id])
        visited = set([id])

        current_level = 0

        while queue and current_level < level:
            level_size = len(queue)

            for _ in range(level_size):
                person = queue.popleft()

                for friend in friends[person]:
                    if friend not in visited:
                        visited.add(friend)
                        queue.append(friend)

            current_level += 1

        frequency = defaultdict(int)

        for person in queue:
            for video in watchedVideos[person]:
                frequency[video] += 1

        return sorted(frequency.keys(), key=lambda x: (frequency[x], x))

sol = Solution()

# Example 1
assert sol.watchedVideosByFriends(
    [["A","B"],["C"],["B","C"],["D"]],
    [[1,2],[0,3],[0,3],[1,2]],
    0,
    1
) == ["B", "C"]  # basic BFS level 1 case

# Example 2
assert sol.watchedVideosByFriends(
    [["A","B"],["C"],["B","C"],["D"]],
    [[1,2],[0,3],[0,3],[1,2]],
    0,
    2
) == ["D"]  # deeper BFS level

# Tie frequency, alphabetical ordering
assert sol.watchedVideosByFriends(
    [["A"],["B"],["C"]],
    [[1],[0,2],[1]],
    0,
    2
) == ["C"]  # single node at target level

# Multiple videos with same frequency
assert sol.watchedVideosByFriends(
    [["A"],["B","C"],["C","B"]],
    [[1,2],[0],[0]],
    0,
    1
) == ["B", "C"]  # alphabetical tie breaking

# Cycle graph
assert sol.watchedVideosByFriends(
    [["A"],["B"],["C"],["D"]],
    [[1,3],[0,2],[1,3],[0,2]],
    0,
    2
) == ["C"]  # verifies visited handling

# Larger level traversal
assert sol.watchedVideosByFriends(
    [["A"],["B"],["C"],["D"],["E"]],
    [[1],[0,2],[1,3],[2,4],[3]],
    0,
    4
) == ["E"]  # long chain traversal

# Duplicate videos counted correctly
assert sol.watchedVideosByFriends(
    [["A"],["X"],["X"]],
    [[1,2],[0],[0]],
    0,
    1
) == ["X"]  # frequency aggregation

# Complex frequency ordering
assert sol.watchedVideosByFriends(
    [["A"],["B","C"],["B","D"],["C","D"]],
    [[1,2],[0,3],[0,3],[1,2]],
    0,
    1
) == ["C", "D", "B"]  # mixed frequencies

Test	Why
Example 1	Validates standard BFS level traversal
Example 2	Validates deeper shortest path handling
Single target node	Ensures exact level matching
Equal frequencies	Confirms alphabetical tie breaking
Cycle graph	Ensures visited tracking prevents revisits
Long chain	Tests multiple BFS layers
Duplicate video counting	Verifies frequency accumulation
Mixed frequency ordering	Tests combined sorting conditions

Edge Cases

One important edge case occurs when the friendship graph contains cycles. Without a visited set, BFS could repeatedly revisit the same people and potentially enter an infinite loop. The implementation avoids this by marking each person as visited immediately when discovered.

Another subtle case involves videos with identical frequencies. The problem requires alphabetical ordering when counts tie. A naive implementation that sorts only by frequency would fail these cases. The solution explicitly sorts using a tuple of (frequency, video_name) to guarantee correct secondary ordering.

A third important edge case happens when multiple friendship paths exist to the same person. Since the problem defines levels using the shortest path distance, a person should appear only at their minimum distance from the starting node. BFS naturally guarantees this property because nodes are first discovered at their shortest possible distance, and the visited set prevents later rediscovery through longer paths.