Get Watched Videos by Your Friends

Med

#1220Time: O(N + E + V_total * log(V_total) + U * log(U)), where N is people, E is friendships, V_total is total videos watched by level-k friends, and U is unique videos. BFS is O(N + E). Sorting all videos is the bottleneck at O(V_total * log(V_total)).Space: O(N + V_total), where N is the number of people and V_total is the total number of video instances. The BFS queue and visited array take O(N) space. The `allVideos` list takes O(V_total) space.1 company

Algorithms

Sorting Breadth-First Search

Data structures

Array Hash Table Graph

Companies

Guidewire

Prompt

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.

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"] 
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:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach first identifies the friends at the specified level using a Breadth-First Search (BFS). BFS is ideal for finding all nodes at a specific distance from a source node in an unweighted graph. After finding the target friends, it collects all their watched videos into a single list. To count frequencies, it first sorts this list of videos alphabetically. This groups identical videos together, making it easy to count them in a single pass. The resulting video-frequency pairs are then sorted again based on the problem's criteria (by frequency, then alphabetically).

Algorithm

1. Initialize a queue for BFS with id and a visited set containing id.
1. Initialize currentLevel = 0.
1. While the queue is not empty and currentLevel < level:
- a. Get the size of the queue for the current level.
- b. For i from 0 to size-1:
  - i. Dequeue a person u.
  - ii. For each friend v of u:
    - If v is not in visited:
      - Add v to visited.
      - Enqueue v.
- c. Increment currentLevel.
1. The people remaining in the queue are the friends at the target level. If the queue is empty, return an empty list.
1. Create an empty list allVideos.
1. For each person p in the queue, add all their watched videos to allVideos.
1. Sort allVideos alphabetically.
1. Create a list of pairs videoFrequencies.
1. Iterate through the sorted allVideos to count frequencies and populate videoFrequencies.
1. Sort videoFrequencies first by frequency (ascending) and then by video name (alphabetical).
1. Extract the video names from the sorted videoFrequencies list and return it.

Walkthrough

The process is divided into two main phases:

Finding Friends at level:
- A queue is initialized with the starting id.
- A visited array or set is used to keep track of people already processed to avoid cycles and redundant computations.
- The BFS proceeds in levels. We iterate level times. In each iteration, we process all the people currently in the queue (a single "level" of friends), and add their unvisited friends to the queue for the next level.
- After level iterations, the people remaining in the queue are exactly at the shortest distance of level from the starting id.
Collecting, Counting, and Sorting Videos:
- All videos watched by the friends found in the previous step are aggregated into one large list.
- This list is sorted alphabetically. For example, ["C", "B", "C"] becomes ["B", "C", "C"].
- We then iterate through this sorted list to count the frequency of each unique video. We can do this by keeping track of the current video and a counter. When the video changes, we store the previous video and its count.
- The list of (video, frequency) pairs is stored.
- Finally, this list of pairs is sorted. The primary sorting key is the frequency (ascending), and the secondary key is the video name (alphabetical).
- The sorted video names are extracted into the final result list.

1import java.util.*;2 3class Solution {4    public List<String> getWatchedVideosByYourFriends(List<List<String>> watchedVideos, int[][] friends, int id, int level) {5        // Step 1: BFS to find friends at the given level6        Queue<Integer> queue = new LinkedList<>();7        queue.offer(id);8        boolean[] visited = new boolean[friends.length];9        visited[id] = true;10        11        int currentLevel = 0;12        while (!queue.isEmpty() && currentLevel < level) {13            int size = queue.size();14            for (int i = 0; i < size; i++) {15                int person = queue.poll();16                for (int friend : friends[person]) {17                    if (!visited[friend]) {18                        visited[friend] = true;19                        queue.offer(friend);20                    }21                }22            }23            currentLevel++;24        }25        26        // Step 2: Collect all videos from friends at the target level27        List<String> allVideos = new ArrayList<>();28        while (!queue.isEmpty()) {29            allVideos.addAll(watchedVideos.get(queue.poll()));30        }31        32        if (allVideos.isEmpty()) {33            return new ArrayList<>();34        }35        36        // Step 3: Sort videos to count frequencies37        Collections.sort(allVideos);38        39        // Step 4: Count frequencies40        List<Map.Entry<String, Integer>> freqList = new ArrayList<>();41        if (!allVideos.isEmpty()) {42            int count = 1;43            for (int i = 1; i < allVideos.size(); i++) {44                if (allVideos.get(i).equals(allVideos.get(i - 1))) {45                    count++;46                } else {47                    freqList.add(new AbstractMap.SimpleEntry<>(allVideos.get(i - 1), count));48                    count = 1;49                }50            }51            freqList.add(new AbstractMap.SimpleEntry<>(allVideos.get(allVideos.size() - 1), count));52        }53 54        // Step 5: Sort by frequency, then by name55        Collections.sort(freqList, (a, b) -> {56            if (a.getValue().equals(b.getValue())) {57                return a.getKey().compareTo(b.getKey());58            }59            return a.getValue() - b.getValue();60        });61        62        // Step 6: Extract sorted video names63        List<String> result = new ArrayList<>();64        for (Map.Entry<String, Integer> entry : freqList) {65            result.add(entry.getKey());66        }67        68        return result;69    }70}

Complexity

Time

O(N + E + V_total * log(V_total) + U * log(U)), where N is people, E is friendships, V_total is total videos watched by level-k friends, and U is unique videos. BFS is O(N + E). Sorting all videos is the bottleneck at O(V_total * log(V_total)).

Space

O(N + V_total), where N is the number of people and V_total is the total number of video instances. The BFS queue and visited array take O(N) space. The `allVideos` list takes O(V_total) space.

Trade-offs

Pros

Correctly solves the problem.
The BFS part is efficient for finding the friends.

Cons

The frequency counting method is inefficient. Sorting the entire list of videos (V_total) can be slow if there are many videos and many friends.
Requires multiple passes over the video data and multiple sorting operations.
Uses more intermediate memory for the allVideos list compared to a map-based approach.

This approach is the most efficient way to solve the problem. It also starts with a Breadth-First Search (BFS) to find the friends at the exact specified level. However, it improves upon the video processing part. Instead of collecting all videos into a list and sorting it, this method uses a Hash Map to count the frequencies of the videos in a single pass. This avoids the costly step of sorting all video occurrences. After counting, the map entries are converted to a list and sorted just once according to the problem's requirements.

Algorithm

1. Initialize a queue for BFS with id and a visited set containing id.
1. Initialize currentLevel = 0.
1. While the queue is not empty and currentLevel < level:
- a. Get the size of the queue for the current level.
- b. For i from 0 to size-1:
  - i. Dequeue a person u.
  - ii. For each friend v of u:
    - If v is not in visited:
      - Add v to visited.
      - Enqueue v.
- c. Increment currentLevel.
1. The people remaining in the queue are the friends at the target level.
1. Create an empty Hash Map videoFrequencies to store (video, count).
1. For each person p in the queue:
- For each video in watchedVideos[p]:
  - Increment the count for video in the videoFrequencies map.
1. Create a list from the entries of the videoFrequencies map.
1. Sort this list using a custom comparator: first by frequency (ascending), then by video name (alphabetical).
1. Create the final result list by adding the video names from the sorted list of entries.
1. Return the result list.

Walkthrough

The overall structure is similar to the first approach but with a more optimized second phase.

Finding Friends at level:
- This part is identical to the first approach. A standard BFS is performed for level steps to find all people at the shortest distance of level from id. A queue and a visited set are used.
Collecting, Counting, and Sorting Videos using a Hash Map:
- A Hash Map (Map<String, Integer>) is created to store video frequencies.
- We iterate through the list of friends at the target level. For each friend, we iterate through their list of watched videos.
- For each video, we update its count in the hash map. map.put(video, map.getOrDefault(video, 0) + 1). This single pass builds a complete frequency count of all relevant videos.
- After populating the map, we extract its keys into a list.
- This list is then sorted using a custom comparator that looks up frequencies in the map. The comparator first compares entries by frequency (ascending) and then by video name (alphabetical) for ties.
- Finally, the sorted list of video names is returned.

1import java.util.*;2 3class Solution {4    public List<String> getWatchedVideosByYourFriends(List<List<String>> watchedVideos, int[][] friends, int id, int level) {5        // Step 1: BFS to find friends at the given level6        Queue<Integer> queue = new LinkedList<>();7        queue.offer(id);8        boolean[] visited = new boolean[friends.length];9        visited[id] = true;10        11        int currentLevel = 0;12        while (!queue.isEmpty() && currentLevel < level) {13            int size = queue.size();14            for (int i = 0; i < size; i++) {15                int person = queue.poll();16                for (int friend : friends[person]) {17                    if (!visited[friend]) {18                        visited[friend] = true;19                        queue.offer(friend);20                    }21                }22            }23            currentLevel++;24        }25        26        // Step 2: Use a HashMap to count video frequencies27        Map<String, Integer> freqMap = new HashMap<>();28        while (!queue.isEmpty()) {29            int person = queue.poll();30            for (String video : watchedVideos.get(person)) {31                freqMap.put(video, freqMap.getOrDefault(video, 0) + 1);32            }33        }34        35        // Step 3: Create a list of videos from the map keys36        List<String> result = new ArrayList<>(freqMap.keySet());37        38        // Step 4: Sort the list with a custom comparator39        Collections.sort(result, (a, b) -> {40            int freqA = freqMap.get(a);41            int freqB = freqMap.get(b);42            if (freqA != freqB) {43                return freqA - freqB;44            }45            return a.compareTo(b);46        });47        48        return result;49    }50}

Complexity

Time

O(N + E + V_total + U * log(U)), where N is people, E is friendships, V_total is total videos, and U is unique videos. BFS is O(N + E). Populating the map is O(V_total). Sorting unique videos is O(U * log(U)). This is faster as U <= V_total.

Space

O(N + U), where N is the number of people and U is the number of unique videos. The BFS structures take O(N) space. The frequency map and result list take O(U) space.

Trade-offs

Pros

Most efficient time complexity. The frequency counting is done in linear time with respect to the total number of videos.
Optimal space complexity, as it only stores unique videos in the map.
The logic is clean and follows standard patterns for graph traversal and frequency counting.

Cons

No significant cons; this is the standard and best approach for this problem.

Solutions

Solution

1class Solution {2public3  List<String> watchedVideosByFriends(List<List<String>> watchedVideos,4                                      int[][] friends, int id, int level) {5    int n = friends.length;6    boolean[] vis = new boolean[n];7    Deque<Integer> q = new LinkedList<>();8    q.offerLast(id);9    vis[id] = true;10    while (level-- > 0) {11      for (int i = q.size(); i > 0; --i) {12        int u = q.pollFirst();13        for (int v : friends[u]) {14          if (!vis[v]) {15            q.offerLast(v);16            vis[v] = true;17          }18        }19      }20    }21    Map<String, Integer> freq = new HashMap<>();22    while (!q.isEmpty()) {23      for (String w : watchedVideos.get(q.pollFirst())) {24        freq.put(w, freq.getOrDefault(w, 0) + 1);25      }26    }27    List<Map.Entry<String, Integer>> t = new ArrayList<>(freq.entrySet());28    t.sort((a, b)->{29      if (a.getValue() > b.getValue()) {30        return 1;31      }32      if (a.getValue() < b.getValue()) {33        return -1;34      }35      return a.getKey().compareTo(b.getKey());36    });37    List<String> ans = new ArrayList<>();38    for (Map.Entry<String, Integer> e : t) {39      ans.add(e.getKey());40    }41    return ans;42  }43}

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

1class Solution:2    def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int, ) -> List[str]: n = len(friends) vis = [False] * n q = deque([id]) vis[id] = True for _ in range(level): size = len(q) for _ in range(size): u = q . popleft() for v in friends[u]: if not vis[v]: q . append(v) vis[v] = True freq = Counter() for _ in range(len(q)): u = q . pop() for w in watchedVideos[u]: freq[w] += 1 videos = list(freq . items()) videos . sort(key=lambda x: (x[1], x[0])) return [v[0] for v in videos]

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem