Problem

There are n people, each person has a unique id between 0 and n-1. Given the arrays watchedVideos and friends, where watchedVideos[i] and friends[i] contain the list of watched videos and the list of friends respectively for the person with id = i.

Level 1 of videos are all watched videos by your friends, level 2 of videos are all watched videos by the friends of your friends and so on. In general, the level k of videos are all watched videos by people with the shortest path exactly equal to k with you. Given your id and the level of videos, return the list of videos ordered by their frequencies (increasing). For videos with the same frequency order them alphabetically from least to greatest.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


**![](https://assets.leetcode.com/uploads/2020/01/02/leetcode_friends_1.png)**

Input: watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 1
Output: ["B","C"] 
Explanation: 
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

1
2
3
4
5
6
7


**![](https://assets.leetcode.com/uploads/2020/01/02/leetcode_friends_2.png)**

Input: watchedVideos = [["A","B"],["C"],["B","C"],["D"]], friends = [[1,2],[0,3],[0,3],[1,2]], id = 0, level = 2
Output: ["D"]
Explanation: 
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

Method 1 – BFS and Frequency Counting

Intuition

We need to find all friends at a specific level using BFS (Breadth-First Search) starting from the given person. Then, we collect all videos watched by these friends, count their frequencies, and return the list sorted by frequency and then alphabetically.

Approach

  1. Use BFS to find all friends at the given level:
    • Start from the given id.
    • For each level, visit all friends of the current set, avoiding revisiting.
    • After level steps, collect all friends at that level.
  2. For each friend at the target level, collect their watched videos and count frequencies.
  3. Sort the videos by frequency (ascending), then alphabetically.
  4. Return the sorted list.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
public:
    vector<string> watchedVideosByFriends(vector<vector<string>>& watchedVideos, vector<vector<int>>& friends, int id, int level) {
        int n = friends.size();
        vector<bool> visited(n, false);
        queue<int> q;
        q.push(id);
        visited[id] = true;
        int currLevel = 0;
        while (!q.empty() && currLevel < level) {
            int sz = q.size();
            for (int i = 0; i < sz; ++i) {
                int u = q.front(); q.pop();
                for (int v : friends[u]) {
                    if (!visited[v]) {
                        visited[v] = true;
                        q.push(v);
                    }
                }
            }
            currLevel++;
        }
        unordered_map<string, int> freq;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (const string& vid : watchedVideos[u]) {
                freq[vid]++;
            }
        }
        vector<pair<string, int>> vids(freq.begin(), freq.end());
        sort(vids.begin(), vids.end(), [](auto& a, auto& b) {
            return a.second == b.second ? a.first < b.first : a.second < b.second;
        });
        vector<string> ans;
        for (auto& p : vids) ans.push_back(p.first);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

func watchedVideosByFriends(watchedVideos [][]string, friends [][]int, id int, level int) []string {
    n := len(friends)
    visited := make([]bool, n)
    q := []int{id}
    visited[id] = true
    for l := 0; l < level; l++ {
        next := []int{}
        for _, u := range q {
            for _, v := range friends[u] {
                if !visited[v] {
                    visited[v] = true
                    next = append(next, v)
                }
            }
        }
        q = next
    }
    freq := map[string]int{}
    for _, u := range q {
        for _, vid := range watchedVideos[u] {
            freq[vid]++
        }
    }
    type pair struct{ vid string; cnt int }
    vids := []pair{}
    for k, v := range freq {
        vids = append(vids, pair{k, v})
    }
    sort.Slice(vids, func(i, j int) bool {
        if vids[i].cnt == vids[j].cnt {
            return vids[i].vid < vids[j].vid
        }
        return vids[i].cnt < vids[j].cnt
    })
    ans := []string{}
    for _, p := range vids {
        ans = append(ans, p.vid)
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Solution {
    public List<String> watchedVideosByFriends(List<List<String>> watchedVideos, List<List<Integer>> friends, int id, int level) {
        int n = friends.size();
        boolean[] visited = new boolean[n];
        Queue<Integer> q = new LinkedList<>();
        q.offer(id);
        visited[id] = true;
        int currLevel = 0;
        while (!q.isEmpty() && currLevel < level) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                int u = q.poll();
                for (int v : friends.get(u)) {
                    if (!visited[v]) {
                        visited[v] = true;
                        q.offer(v);
                    }
                }
            }
            currLevel++;
        }
        Map<String, Integer> freq = new HashMap<>();
        for (int u : q) {
            for (String vid : watchedVideos.get(u)) {
                freq.put(vid, freq.getOrDefault(vid, 0) + 1);
            }
        }
        List<String> ans = new ArrayList<>(freq.keySet());
        ans.sort((a, b) -> freq.get(a).equals(freq.get(b)) ? a.compareTo(b) : freq.get(a) - freq.get(b));
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    fun watchedVideosByFriends(watchedVideos: List<List<String>>, friends: List<List<Int>>, id: Int, level: Int): List<String> {
        val n = friends.size
        val visited = BooleanArray(n)
        var q = mutableListOf(id)
        visited[id] = true
        repeat(level) {
            val next = mutableListOf<Int>()
            for (u in q) {
                for (v in friends[u]) {
                    if (!visited[v]) {
                        visited[v] = true
                        next.add(v)
                    }
                }
            }
            q = next
        }
        val freq = mutableMapOf<String, Int>()
        for (u in q) {
            for (vid in watchedVideos[u]) {
                freq[vid] = freq.getOrDefault(vid, 0) + 1
            }
        }
        return freq.entries.sortedWith(compareBy({ it.value }, { it.key })).map { it.key }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def watchedVideosByFriends(self, watchedVideos: list[list[str]], friends: list[list[int]], id: int, level: int) -> list[str]:
        from collections import deque, Counter
        n = len(friends)
        visited = [False] * n
        q = deque([id])
        visited[id] = True
        curr_level = 0
        while q and curr_level < level:
            for _ in range(len(q)):
                u = q.popleft()
                for v in friends[u]:
                    if not visited[v]:
                        visited[v] = True
                        q.append(v)
            curr_level += 1
        freq = Counter()
        for u in q:
            freq.update(watchedVideos[u])
        return sorted(freq, key=lambda x: (freq[x], x))
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

impl Solution {
    pub fn watched_videos_by_friends(watched_videos: Vec<Vec<String>>, friends: Vec<Vec<i32>>, id: i32, level: i32) -> Vec<String> {
        use std::collections::{VecDeque, HashSet, HashMap};
        let n = friends.len();
        let mut visited = vec![false; n];
        let mut q = VecDeque::new();
        q.push_back(id as usize);
        visited[id as usize] = true;
        let mut curr_level = 0;
        while !q.is_empty() && curr_level < level {
            for _ in 0..q.len() {
                let u = q.pop_front().unwrap();
                for &v in &friends[u] {
                    let v = v as usize;
                    if !visited[v] {
                        visited[v] = true;
                        q.push_back(v);
                    }
                }
            }
            curr_level += 1;
        }
        let mut freq = HashMap::new();
        for &u in &q {
            for vid in &watched_videos[u] {
                *freq.entry(vid.clone()).or_insert(0) += 1;
            }
        }
        let mut vids: Vec<_> = freq.into_iter().collect();
        vids.sort_by(|a, b| a.1.cmp(&b.1).then(a.0.cmp(&b.0)));
        vids.into_iter().map(|(k, _)| k).collect()
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    watchedVideosByFriends(watchedVideos: string[][], friends: number[][], id: number, level: number): string[] {
        const n = friends.length;
        const visited = Array(n).fill(false);
        let q: number[] = [id];
        visited[id] = true;
        for (let l = 0; l < level; l++) {
            const next: number[] = [];
            for (const u of q) {
                for (const v of friends[u]) {
                    if (!visited[v]) {
                        visited[v] = true;
                        next.push(v);
                    }
                }
            }
            q = next;
        }
        const freq: Record<string, number> = {};
        for (const u of q) {
            for (const vid of watchedVideos[u]) {
                freq[vid] = (freq[vid] || 0) + 1;
            }
        }
        return Object.keys(freq).sort((a, b) => freq[a] - freq[b] || a.localeCompare(b));
    }
}

Complexity

  • ⏰ Time complexity: O(n + m log m) — BFS visits each person once (O(n)), and sorting the videos by frequency and name takes O(m log m) where m is the number of unique videos.
  • 🧺 Space complexity: O(n + m) — For visited array, queue, and frequency map.