You are given a list of users, where each user has a list of friends and a list of videos they have watched. The information is represented as:
watchedVideos: A list where watchedVideos[i] is a list of strings representing videos watched by the i-th user.friends: A list where friends[i] is a list of user IDs (integers) representing the friends of the i-th user.id: The ID of the starting user.level: The friendship level to consider.
Your task is: Find all the videos watched by friends at exactly level friendship distance from the given user id. Return a sorted list of video names ordered first by the frequency of viewing (ascending), then lexicographically.
Key constraints:
The core of the problem is to find all friends at a specific distance (level) from a given user and aggregate the videos they have watched. The naive approach would be to look through all users and check their distance, but this is inefficient and error-prone. Instead, we can model the friendship network as a graph and use Breadth-First Search (BFS) to find all friends at the required level.
Once we have the correct set of friends, we gather their watched videos and count their frequencies. Sorting the results by frequency and then by name ensures the answer is in the right order.
Optimization comes from:
Let's break down the solution into clear steps:
id.level.We use BFS because it naturally explores nodes in order of their distance from the starting node, making it ideal for "level"-based problems in graphs.
Consider the following example:
watchedVideos = [["A","B"],["C"],["B","C"],["D"]]friends = [[1,2],[0,3],[0,3],[1,2]]id = 0level = 1Steps:
At each BFS level, we only expand friends who haven't been visited yet, ensuring we don't count the same user twice.
Brute-force Approach:
Using BFS ensures we only visit each user once, and the hash map makes counting efficient.
This problem combines graph traversal with frequency counting and custom sorting. By modeling friendships as a graph and using BFS, we efficiently find all friends at the required level. Hash maps allow quick aggregation of video counts, and a simple sort gives us the required output order. The approach is both efficient and elegant, leveraging standard graph algorithms and data structures to solve a real-world scenario.
from collections import deque, Counter
class Solution:
def watchedVideosByFriends(self, watchedVideos, friends, id, level):
n = len(friends)
visited = set()
queue = deque()
queue.append(id)
visited.add(id)
curr_level = 0
while queue and curr_level < level:
for _ in range(len(queue)):
user = queue.popleft()
for f in friends[user]:
if f not in visited:
visited.add(f)
queue.append(f)
curr_level += 1
# queue now contains users at the exact 'level'
freq = Counter()
for user in queue:
freq.update(watchedVideos[user])
result = sorted(freq.items(), key=lambda x: (x[1], x[0]))
return [video for video, _ in result]
#include <vector>
#include <string>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
using namespace std;
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 curr_level = 0;
while (!q.empty() && curr_level < level) {
int sz = q.size();
for (int i = 0; i < sz; ++i) {
int user = q.front(); q.pop();
for (int f : friends[user]) {
if (!visited[f]) {
visited[f] = true;
q.push(f);
}
}
}
curr_level++;
}
unordered_map<string, int> freq;
while (!q.empty()) {
int user = q.front(); q.pop();
for (const string& video : watchedVideos[user]) {
freq[video]++;
}
}
vector<pair<string, int>> vids(freq.begin(), freq.end());
sort(vids.begin(), vids.end(), [](const pair<string, int>& a, const pair<string, int>& b) {
if (a.second == b.second) return a.first < b.first;
return a.second < b.second;
});
vector<string> result;
for (const auto& p : vids) result.push_back(p.first);
return result;
}
};
import java.util.*;
class Solution {
public List<String> watchedVideosByFriends(List<List<String>> watchedVideos, List<List<Integer>> friends, int id, int level) {
int n = friends.size();
Queue<Integer> queue = new LinkedList<>();
boolean[] visited = new boolean[n];
queue.offer(id);
visited[id] = true;
int currLevel = 0;
while (!queue.isEmpty() && currLevel < level) {
int sz = queue.size();
for (int i = 0; i < sz; i++) {
int user = queue.poll();
for (int f : friends.get(user)) {
if (!visited[f]) {
visited[f] = true;
queue.offer(f);
}
}
}
currLevel++;
}
Map<String, Integer> freq = new HashMap<>();
for (int user : queue) {
for (String video : watchedVideos.get(user)) {
freq.put(video, freq.getOrDefault(video, 0) + 1);
}
}
List<String> result = new ArrayList<>(freq.keySet());
result.sort((a, b) -> {
int cmp = freq.get(a) - freq.get(b);
if (cmp == 0) return a.compareTo(b);
return cmp;
});
return result;
}
}
/**
* @param {string[][]} watchedVideos
* @param {number[][]} friends
* @param {number} id
* @param {number} level
* @return {string[]}
*/
var watchedVideosByFriends = function(watchedVideos, friends, id, level) {
let n = friends.length;
let visited = new Array(n).fill(false);
let queue = [id];
visited[id] = true;
let currLevel = 0;
while (queue.length > 0 && currLevel < level) {
let sz = queue.length;
for (let i = 0; i < sz; i++) {
let user = queue.shift();
for (let f of friends[user]) {
if (!visited[f]) {
visited[f] = true;
queue.push(f);
}
}
}
currLevel++;
}
let freq = {};
for (let user of queue) {
for (let video of watchedVideos[user]) {
freq[video] = (freq[video] || 0) + 1;
}
}
let vids = Object.keys(freq);
vids.sort((a, b) => {
if (freq[a] === freq[b]) return a.localeCompare(b);
return freq[a] - freq[b];
});
return vids;
};