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

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Graph algorithms

Graph traversal

Sorting

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

Solutions:
class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		vis = [0 for i in range(len(friends))]
		index = id
		lis = set([id])
		while level > 0:
			temp = []
			for i in lis:
				if vis[i] == 0:
					temp += friends[i]
					vis[i] = 1
			lis = set(temp)
			level -= 1
		dic = dict()
		for i in lis:
			if vis[i] == 0:
				for j in watchedVideos[i]:
					if j in dic:
						dic[j] += 1
					else:
						dic[j] = 1
		dic2 = dict()
		for i in dic:
			if dic[i] in dic2:
				dic2[dic[i]].append(i)
			else:
				dic2[dic[i]] = [i]
		lis = []
		for i in sorted(dic2.keys()):
			lis += sorted(dic2[i])
		return lis


from collections import deque, Counter

class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		all_video = 0
		videos_dict = {}
		queue = deque([id])
		visited = set()
		visited.add(id)
		current_level = 0
		friends_dict = {id: []}
		while queue:
			level_size = len(queue)
			level_friends = queue
			for _ in range(level_size):
				cur_node = queue.popleft()
				for friend in friends[cur_node]:
					if friend in visited:
						continue
					queue.append(friend)
					visited.add(friend)
			current_level += 1
			print(current_level)
			if current_level == level:
				break
		print(('friends', queue))
		for friend in queue:
			for video in watchedVideos[friend]:
				if video in videos_dict:
					videos_dict[video] += 1
				else:
					videos_dict[video] = 1
		return sorted(videos_dict, key=lambda x: (videos_dict[x], x), reverse=False)


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		n = len(watchedVideos)
		dist = [9999] * n
		queue = [(id, 0)]
		while queue:
			(idx, depth) = queue.pop(0)
			if depth < dist[idx]:
				dist[idx] = depth
				for c in friends[idx]:
					queue.append((c, depth + 1))
		freq = defaultdict(int)
		for (i, l) in enumerate(dist):
			if l == level:
				for vid in watchedVideos[i]:
					freq[vid] += 1
		pairs = sorted([(v, k) for (k, v) in list(freq.items())])
		return [x[-1] for x in pairs]


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		frontier = [id]
		seen = {id}
		depth = 0
		while frontier:
			next_frontier = []
			if depth == level - 1:
				count = collections.defaultdict(lambda : 0)
			for p in frontier:
				for fr in friends[p]:
					if fr not in seen:
						seen.add(fr)
						if depth == level - 1:
							for video in watchedVideos[fr]:
								count[video] += 1
						next_frontier.append(fr)
			frontier = next_frontier
			depth += 1
			if depth == level:
				return sorted(count.keys(), key=lambda x: [count[x], x])
		return []


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		(bfs, visited) = ({id}, {id})
		for _ in range(level):
			bfs = {j for i in bfs for j in friends[i] if j not in visited}
			visited |= bfs
		freq = collections.Counter([v for idx in bfs for v in watchedVideos[idx]])
		return sorted(list(freq.keys()), key=lambda x: (freq[x], x))


class Solution:

	def bfs(self, id: int, target_level: int, friends: List[List[int]], watchedVideos: List[List[str]], ans: dict):
		queue = []
		visited = []
		valid_index = 0
		queue.insert(0, id)
		visited.append(id)
		for l in range(target_level):
			new_q = []
			while len(queue) != 0:
				k = queue[0]
				del queue[0]
				for i in friends[k]:
					if i not in visited:
						visited.append(i)
						new_q.append(i)
			queue[:] = new_q
		for f in queue:
			for v in watchedVideos[f]:
				if v not in ans:
					ans[v] = 1
				else:
					ans[v] += 1

	def dfs(self, id: int, cur_level: int, target_level: int, friends: List[List[int]], watchedVideos: List[List[str]], ans: dict, visited: List[int]):
		if id in visited:
			return
		visited.append(id)
		if cur_level == target_level:
			for v in watchedVideos[id]:
				if v not in ans:
					ans[v] = 1
				else:
					ans[v] += 1
			return
		for f in friends[id]:
			self.dfs(f, cur_level + 1, target_level, friends, watchedVideos, ans, visited)

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		ans = {}
		self.bfs(id, level, friends, watchedVideos, ans)
		ret = [k for (k, v) in sorted(list(ans.items()), key=lambda item: (item[1], item[0]))]
		return ret


from collections import defaultdict

class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		graph = defaultdict(list)
		for (i, friend_list) in enumerate(friends):
			for friend in friend_list:
				graph[i].append(friend)
				graph[friend].append(i)
		queue = [id]
		visited = set()
		visited.add(id)
		current_level = 0
		videos = defaultdict(lambda : 0)
		while queue:
			if current_level == level:
				for friend in queue:
					for video in watchedVideos[friend]:
						videos[video] += 1
				break
			size = len(queue)
			for i in range(size):
				node = queue.pop(0)
				for friend in graph[node]:
					if friend not in visited:
						visited.add(friend)
						queue.append(friend)
			current_level += 1
		answer = sorted(list(videos.keys()), key=lambda x: (videos[x], x))
		return answer


class Solution:

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

		def bfs(start):
			queue = [start]
			current_level = 0
			visited = set()
			while queue:
				if current_level >= level:
					break
				subqueue = queue[:]
				queue = []
				for i in subqueue:
					visited.add(i)
					for j in friends[i]:
						if j not in visited and j not in queue and (j not in subqueue):
							queue.append(j)
				current_level += 1
			return queue
		from collections import Counter
		import heapq
		videos = []
		for i in bfs(id):
			videos += watchedVideos[i]
		freq = dict(Counter(videos))
		heap = []
		for key in freq:
			heapq.heappush(heap, (freq[key], key))
		ans = []
		while heap:
			ans.append(heapq.heappop(heap)[1])
		return ans


from collections import defaultdict
import heapq

class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		adj = {}
		for i in range(len(friends)):
			adj[i] = friends[i]
		queue = [id]
		visited = set()
		visited.add(id)
		dis = 0
		while queue:
			if dis == level:
				break
			for _ in range(len(queue)):
				cur = queue.pop(0)
				for friend in adj[cur]:
					if friend not in visited:
						queue.append(friend)
						visited.add(friend)
			dis += 1
		count = defaultdict(int)
		for people in queue:
			for video in watchedVideos[people]:
				count[video] += 1
		heap = []
		for key in count:
			heapq.heappush(heap, (count[key], key))
		res = []
		while heap:
			res.append(heapq.heappop(heap)[1])
		return res


from collections import defaultdict

class Movie:

	def __init__(self, name):
		self.name = name
		self.freq = 0

	def __lt__(self, other):
		if not other:
			return True
		if self.freq != other.freq:
			return self.freq < other.freq
		return self.name < other.name

class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		if not watchedVideos or not friends or level == 0:
			return []
		movies_freq = {}
		queue = deque()
		queue.append(id)
		cur_level = 0
		visited = set()
		visited.add(id)
		while queue:
			n = len(queue)
			if cur_level == level:
				break
			cur_level += 1
			for _ in range(n):
				node = queue.popleft()
				if node >= len(friends):
					continue
				for child in friends[node]:
					if child in visited:
						continue
					visited.add(child)
					queue.append(child)
		print(queue)
		while queue:
			friend = queue.popleft()
			if friend >= len(watchedVideos):
				continue
			for video in watchedVideos[friend]:
				if video not in movies_freq:
					video_obj = Movie(video)
					movies_freq[video] = video_obj
				movies_freq[video].freq += 1
		if not movies_freq:
			return []
		(*result,) = [x.name for x in sorted(movies_freq.values())]
		return result


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		(w, f) = ({}, {})
		for i in range(len(friends)):
			w[i] = watchedVideos[i]
			f[i] = friends[i]
		cand = []
		frontier = [(id, 0)]
		seen = {id}
		while frontier:
			(cur, d) = frontier.pop()
			if d == level:
				cand.append(cur)
				continue
			for friend in f[cur]:
				if friend not in seen:
					seen.add(friend)
					frontier.append((friend, d + 1))
		count = collections.Counter()
		for c in cand:
			for m in w[c]:
				count[m] += 1
		ans = [(v, k) for (k, v) in count.items()]
		ans.sort()
		ans = [x[1] for x in ans]
		return ans


from collections import defaultdict, deque

class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		visited = set()
		queue = deque([(id, 0)])
		visited.add(id)
		chosenFriends = list()
		while queue:
			(person, lv) = queue.popleft()
			if lv == level:
				chosenFriends.append(person)
			if lv > level:
				break
			for friend in friends[person]:
				if friend not in visited:
					queue.append((friend, lv + 1))
					visited.add(friend)
		videoFrequency = defaultdict(int)
		for friend in chosenFriends:
			for video in watchedVideos[friend]:
				videoFrequency[video] += 1
		return [video[0] for video in sorted(list(videoFrequency.items()), key=lambda x: (x[1], x[0]))]


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		graph = collections.defaultdict(list)
		for (u, v) in enumerate(friends):
			for i in v:
				graph[u].append(i)
		queue = collections.deque()
		queue.append((id, 0))
		visited = set()
		visited.add(id)
		res = collections.defaultdict(int)
		while queue:
			(id, l) = queue.popleft()
			if l == level:
				for j in watchedVideos[id]:
					res[j] += 1
			for v in graph[id]:
				if l + 1 <= level and v not in visited:
					visited.add(v)
					queue.append((v, l + 1))
		from functools import cmp_to_key

		def func(x, y):
			if res[x] > res[y]:
				return -1
			elif res[y] > res[x]:
				return 1
			elif x > y:
				return -1
			elif y > x:
				return 1
			else:
				return 0
		return sorted(res.keys(), key=cmp_to_key(func))[::-1]


from collections import Counter

class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		current_level = 0
		nodes_in_current_level = [id]
		visited = set(nodes_in_current_level)
		while current_level < level:
			next_level = []
			while len(nodes_in_current_level) > 0:
				node = nodes_in_current_level.pop()
				for neighbor in friends[node]:
					if neighbor in visited:
						continue
					visited.add(neighbor)
					next_level.append(neighbor)
			nodes_in_current_level = next_level
			current_level += 1
		counter = Counter()
		for id in nodes_in_current_level:
			counter.update(watchedVideos[id])
		return [item for (item, count) in sorted(list(counter.items()), key=lambda x: (x[1], x[0]))]


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		stack = [(0, id)]
		visited = set([id])
		friendsSet = set()
		while stack:
			(lNow, fi) = heapq.heappop(stack)
			if lNow == level:
				friendsSet.add(fi)
			else:
				for fi1 in friends[fi]:
					if fi1 not in visited:
						visited.add(fi1)
						heapq.heappush(stack, (lNow + 1, fi1))
		videoCounter = Counter()
		for f in friendsSet:
			videoCounter += Counter(watchedVideos[f])
		ans = sorted([key for key in videoCounter], key=lambda x: (videoCounter[x], x))
		return ans


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		q = deque([id])
		visited = set()
		visited.add(id)
		for _ in range(level):
			for _ in range(len(q)):
				curr = q.popleft()
				for friend in friends[curr]:
					if friend not in visited:
						q.append(friend)
						visited.add(friend)
		video_dict = {}
		for friend in q:
			for video in watchedVideos[friend]:
				video_dict[video] = video_dict.get(video, 0) + 1
		res = [k for (k, v) in sorted(video_dict.items(), key=lambda item: (item[1], item[0]))]
		return res


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		visited = {id: 1}
		queue = deque()
		queue.append((id, 0))
		result = []
		while queue:
			(u, dist) = queue.popleft()
			if dist == level:
				result.append(u)
				continue
			for v in friends[u]:
				if v in visited:
					continue
				visited[v] = 1
				queue.append((v, dist + 1))
		counter = {}
		for u in result:
			for video in watchedVideos[u]:
				counter[video] = counter.get(video, 0) + 1
		result = sorted([(times, videos) for (videos, times) in list(counter.items())])
		return [val[1] for val in result]


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		n = len(watchedVideos)
		visited = [False] * n
		que = collections.deque([id])
		visited[id] = True
		cur = 0
		while que and cur < level:
			size = len(que)
			cur += 1
			for _ in range(size):
				node = que.popleft()
				for f in friends[node]:
					if not visited[f]:
						visited[f] = True
						que.append(f)
		cnt = collections.Counter()
		for node in que:
			for m in watchedVideos[node]:
				cnt[m] += 1
		videos = list(cnt.keys())
		videos.sort(key=lambda x: [cnt[x], x])
		return videos


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		visited = set()
		queue = deque([(id, 0)])
		visited.add(id)
		requiredFriends = []
		while queue:
			(person, lev) = queue.popleft()
			if lev == level:
				requiredFriends.append(person)
			if lev > level:
				break
			for friend in friends[person]:
				if friend not in visited:
					queue.append((friend, lev + 1))
					visited.add(friend)
		videosFrequency = defaultdict(int)
		for friend in requiredFriends:
			for video in watchedVideos[friend]:
				videosFrequency[video] += 1
		return [video[0] for video in sorted(videosFrequency.items(), key=lambda x: (x[1], x[0]))]


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		g_friends = collections.defaultdict(list)
		for i in range(len(friends)):
			for f in friends[i]:
				g_friends[i].append(f)
		queue = collections.deque()
		queue.append((id, 0))
		visited = set([id])
		videos = collections.defaultdict(int)
		while queue:
			size = len(queue)
			for _ in range(size):
				(curr_id, curr_level) = queue.popleft()
				if curr_level == level:
					for v in watchedVideos[curr_id]:
						videos[v] += 1
				else:
					for f in g_friends[curr_id]:
						if f not in visited:
							visited.add(f)
							queue.append((f, curr_level + 1))
		return [v for (_, v) in sorted([(f, v) for (v, f) in list(videos.items())])]


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		q = deque([id])
		visited = set()
		visited.add(id)
		for _ in range(level):
			for _ in range(len(q)):
				curr = q.popleft()
				for friend in friends[curr]:
					if friend not in visited:
						q.append(friend)
						visited.add(friend)
		video_dict = defaultdict(int)
		for friend in q:
			for video in watchedVideos[friend]:
				video_dict[video] += 1
		res = [k for (k, v) in sorted(list(video_dict.items()), key=lambda item: (item[1], item[0]))]
		return res

	def fast(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int):
		res = []
		visited = [False] * len(friends)
		fr_set = set()
		q = deque([id])
		for _ in range(level):
			size = len(q)
			for n in range(size):
				fId = q.popleft()
				for f in friends[fId]:
					if visited[f] != True and f != id:
						q.append(f)
						visited[f] = True
		dic = {}
		while q:
			fid = q.popleft()
			for video in watchedVideos[fid]:
				dic[video] = dic.get(video, 0) + 1
		res = [k for (k, v) in sorted(list(dic.items()), key=lambda item: (item[1], item[0]))]
		return res


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		graph = defaultdict(list)
		for (i, v) in enumerate(friends):
			graph[i].extend(v)
			for r in v:
				graph[r].append(i)
		videos = defaultdict(int)

		def bfs(source):
			dq = deque([source])
			visited = set()
			visited.add(source)
			nlevels = 0
			while dq:
				for _ in range(len(dq)):
					node = dq.popleft()
					if nlevels == level:
						for v in watchedVideos[node]:
							videos[v] += 1
					for nei in graph[node]:
						if nei not in visited:
							visited.add(nei)
							dq.append(nei)
				nlevels += 1
		bfs(id)
		minheap = []
		for v in sorted(videos.keys()):
			heappush(minheap, (videos[v], v))
		res = []
		while minheap:
			res.append(heappop(minheap)[1])
		return res


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		n = len(friends)
		friend_dist = [math.inf] * n
		friend_dist[id] = 0
		deque = collections.deque()
		deque.append(id)
		watched = dict()
		while deque:
			person = deque.popleft()
			if friend_dist[person] == level:
				for video in watchedVideos[person]:
					watched[video] = watched.get(video, 0) + 1
				continue
			for friend in friends[person]:
				if friend_dist[friend] == math.inf:
					friend_dist[friend] = friend_dist[person] + 1
					deque.append(friend)
		return sorted(watched.keys(), key=lambda v: (watched[v], v))


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		stack = deque([id])
		seen = set()
		seen.add(id)
		for _ in range(level):
			for i in range(len(stack)):
				f = stack.popleft()
				for j in friends[f]:
					if j not in seen:
						stack.append(j)
						seen.add(j)
		count = Counter()
		for lf in stack:
			count += Counter(watchedVideos[lf])
		return [x[0] for x in sorted(count.items(), key=lambda item: (item[1], item[0]))]


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], ID: int, level: int) -> List[str]:
		freqs = dict()
		visited = set()
		visited.add(ID)
		q = set()
		q.add(ID)
		for _ in range(level):
			q = {j for i in q for j in friends[i] if j not in visited}
			visited |= q
		for p in q:
			for v in watchedVideos[p]:
				freqs[v] = freqs.get(v, 0) + 1
		sortedfreqs = sorted([(n, v) for (v, n) in list(freqs.items())])
		return [v for (_, v) in sortedfreqs]


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		visited = set()
		visited.add(id)
		frequency = {}
		dictionary = {}
		q = deque()
		q.append(id)
		running_level = 1
		solution = []
		while q and running_level <= level:
			length = len(q)
			for index in range(length):
				node = q.popleft()
				for friend in friends[node]:
					if friend in visited:
						continue
					visited.add(friend)
					if running_level == level:
						for movie in watchedVideos[friend]:
							frequency[movie] = frequency.get(movie, 0) + 1
					else:
						q.append(friend)
			running_level += 1
		order = set(sorted(frequency.values()))
		for key in frequency:
			dictionary[frequency[key]] = dictionary.get(frequency[key], []) + [key]
		for rank in order:
			solution.extend(sorted(dictionary[rank]))
		return solution


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		n = len(watchedVideos)
		(a, d, w) = ([id], [1] * n, {})
		d[id] = 0
		for _ in range(level):
			b = []
			for i in a:
				for j in friends[i]:
					if d[j]:
						b.append(j)
						d[j] = 0
			a = b
		for i in a:
			for x in watchedVideos[i]:
				w[x] = w.get(x, 0) + 1
		return sorted(w.keys(), key=lambda x: (w[x], x))


from collections import deque, Counter

class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		persons = len(friends)
		visited = [False] * persons
		source = id
		visited[source] = True
		queue = deque()
		queue.append(source)
		k = 0
		videos_counter = Counter()
		while queue and k < level:
			videos_counter = Counter()
			q_len = len(queue)
			for _ in range(q_len):
				person = queue.popleft()
				for friend in friends[person]:
					if visited[friend]:
						continue
					visited[friend] = True
					queue.append(friend)
					videos = watchedVideos[friend]
					for video in videos:
						videos_counter[video] += 1
			k += 1
		frequencies = [(frequency, video) for (video, frequency) in list(videos_counter.items())]
		result = [video for (freq, video) in sorted(frequencies)]
		return result


class Solution:

	def watchedVideosByFriends(self, videos: List[List[str]], friends: List[List[int]], me: int, level: int) -> List[str]:
		visit = set()
		(queue, arr) = ([me], [])
		while level:
			level -= 1
			size = len(queue)
			for i in range(size):
				curr = queue.pop(0)
				if curr not in visit:
					visit.add(curr)
					for f in friends[curr]:
						queue.append(f)
		v = []
		for i in queue:
			if i not in visit:
				visit.add(i)
				v += videos[i]
		c = collections.Counter(v)
		return sorted(sorted(list(set(v))), key=lambda x: c[x])


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		friends = getFriends(friends, id, 1, level, set([id]))
		videoCounts = collections.Counter([val for i in friends for val in watchedVideos[i]])
		sortedCounts = sorted(list(videoCounts.items()), key=lambda video: (video[1], video[0]))
		return [count[0] for count in sortedCounts]

def getFriends(friends: List[List[int]], index: int, level: int, targetLevel: int, knownFriends):
	currentFriends = set(friends[index]) - knownFriends
	if level == targetLevel:
		return currentFriends
	else:
		newKnownFriends = knownFriends | currentFriends
		return set([val for i in currentFriends for val in getFriends(friends, i, level + 1, targetLevel, newKnownFriends)])


from collections import deque, defaultdict

class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		stack = deque()
		nbr = dict()
		stack.append(id)
		seen = set()
		seen.add(id)
		lvl = 0
		while stack:
			n = len(stack)
			lvl += 1
			if lvl > level:
				break
			for i in range(n):
				person_id = stack.pop()
				for p in friends[person_id]:
					if p in seen:
						continue
					seen.add(p)
					stack.append(p)
					if p not in nbr:
						nbr[p] = lvl
		res = defaultdict(int)
		for person_id in nbr:
			if nbr[person_id] == level:
				for video in watchedVideos[person_id]:
					res[video] += 1
		res_sorted = sorted(list(res.items()), key=lambda x: (x[1], x[0]))
		return [x[0] for x in res_sorted]


from collections import Counter

class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		friendsSeen = {id}
		k = 0
		connections = {id}
		for k in range(0, level):
			nextDegree = [friends[i] for i in connections]
			connections = set([friend for friends in nextDegree for friend in friends if friend not in friendsSeen])
			friendsSeen = friendsSeen.union(connections)
		videosWatched = [video for friend in connections for video in watchedVideos[friend]]
		videoCounter = dict(Counter(videosWatched))
		result = sorted(videoCounter.keys(), key=lambda x: videoCounter[x])
		freqUnique = [videoCounter[video] for video in result]
		freqMovieDict = dict()
		for i in range(0, len(freqUnique)):
			if freqUnique[i] not in freqMovieDict:
				freqMovieDict[freqUnique[i]] = [result[i]]
			else:
				freqMovieDict[freqUnique[i]] += [result[i]]
		for key in freqMovieDict:
			freqMovieDict[key] = sorted(freqMovieDict[key])
		ans = []
		for key in sorted(freqMovieDict.keys()):
			ans += freqMovieDict[key]
		return ans


from collections import Counter, deque
from typing import List

class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		q = deque([(0, id)])
		seen = [False] * len(friends)
		d = dict()
		while q:
			(stage, person) = q.popleft()
			seen[person] = True
			if stage not in d:
				d[stage] = set()
			d[stage].add(person)
			for friend in friends[person]:
				if seen[friend]:
					continue
				seen[friend] = True
				q.append((stage + 1, friend))
		shared = dict()
		for friend in d[level]:
			for video in watchedVideos[friend]:
				if video in shared:
					shared[video] += 1
				else:
					shared[video] = 1
		return list((x for (_, x) in sorted(((freq, val) for (val, freq) in shared.items()))))


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		k_friends = self.findFriends(friends, [id], {id}, level)
		watched = {}
		for id in k_friends:
			for vid in watchedVideos[id]:
				if vid in watched:
					watched[vid] += 1
				else:
					watched[vid] = 1
		out = []
		for key in watched:
			out.append((watched[key], key))
		out.sort()
		return list([x[1] for x in out])

	def findFriends(self, friends, ids, seen, level):
		if level == 0 or len(ids) == 0:
			return ids
		new = []
		for id in ids:
			for friend in friends[id]:
				if friend not in seen:
					seen.add(friend)
					new.append(friend)
		return self.findFriends(friends, new, seen, level - 1)


from collections import deque, Counter

class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		n = len(friends)
		stack = deque([id])
		visited = set([id])
		for _ in range(level):
			for j in range(len(stack)):
				cur = stack.popleft()
				for nxt in friends[cur]:
					if nxt not in visited:
						visited.add(nxt)
						stack.append(nxt)
		dic = Counter()
		for ppl in stack:
			dic.update(watchedVideos[ppl])
		items = sorted(list(dic.items()), key=lambda x: (x[1], x[0]))
		return [k for (k, _) in items]


from collections import defaultdict, deque

class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		n = len(friends)
		adj = [[] for i in range(n)]
		for i in range(n):
			adj[i] = friends[i]
		req = []
		visited = {}
		q = deque()
		q.append((id, 0))
		visited[id] = True
		while q:
			(u, lev) = q.popleft()
			if lev == level:
				req.append(u)
				continue
			if lev > level:
				break
			for f in adj[u]:
				if f not in visited:
					q.append((f, lev + 1))
					visited[f] = True
		res = defaultdict(lambda : 0)
		for f in req:
			for mov in watchedVideos[f]:
				res[mov] += 1
		res = sorted(res.items(), key=lambda x: (x[1], x[0]))
		movies = [i[0] for i in res]
		return movies


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		queue = deque()
		queue.append([id, 0])
		ans = defaultdict(int)
		visited = {id: 1}
		while len(queue) > 0:
			(now, l) = queue.popleft()
			if l == level:
				for v in watchedVideos[now]:
					ans[v] += 1
				continue
			for friend in friends[now]:
				if friend not in visited:
					queue.append([friend, l + 1])
					visited[friend] = 1
		ansid = sorted(ans.items(), key=lambda x: (x[1], x[0]))
		ansid = [x for (x, _) in ansid]
		return ansid


import collections

class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		krem = set(range(len(friends)))
		krem.remove(id)
		curlevel = 0
		klevel = set([id])
		while True:
			if curlevel == level:
				break
			newlevel = set()
			for pid in klevel:
				for fid in friends[pid]:
					if not fid in krem:
						continue
					krem.remove(fid)
					newlevel.add(fid)
			klevel = newlevel
			curlevel += 1
		krem = None
		vids = collections.defaultdict(int)
		for pid in klevel:
			for vid in watchedVideos[pid]:
				vids[vid] += 1
		return [x[0] for x in sorted(vids.items(), key=lambda x: (x[1], x[0]))]


class Solution:

	def createAdjMatrix(self, friends):
		adj_mat = {}
		for i in range(len(friends)):
			adj_mat[i] = friends[i]
		return adj_mat

	def calculateFreq(self, level_friend, watchedVideos):
		movies_freq = {}
		for friend in level_friend:
			movies = watchedVideos[friend]
			for movie in movies:
				movies_freq[movie] = movies_freq.get(movie, 0) + 1
		movies_freq = sorted(movies_freq.items(), key=lambda x: (x[1], x[0]))
		movies = [i[0] for i in movies_freq]
		return movies

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		adj_mat = self.createAdjMatrix(friends)
		visited = set()
		Q = [(id, 0)]
		visited.add(id)
		level_friend = []
		while Q and level:
			(id_, lev) = Q.pop(0)
			if lev == level:
				level_friend.append(id_)
			if lev > level:
				break
			friends = adj_mat[id_]
			for friend in friends:
				if friend not in visited:
					Q.append((friend, lev + 1))
					visited.add(friend)
		return self.calculateFreq(level_friend, watchedVideos)


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		graph = collections.defaultdict(set)
		for i in range(len(friends)):
			for friend in friends[i]:
				graph[i].add(friend)
				graph[friend].add(i)
		levelOfFriends = [id]
		visited = set([id])
		l = 0
		while levelOfFriends and l < level:
			size = len(levelOfFriends)
			l += 1
			for _ in range(size):
				f = levelOfFriends.pop(0)
				for otherF in graph[f]:
					if otherF not in visited:
						levelOfFriends.append(otherF)
						visited.add(otherF)
		w = collections.defaultdict(int)
		for f in levelOfFriends:
			videos = watchedVideos[f]
			for v in videos:
				w[v] += 1
		heap = []
		for v in list(w.keys()):
			heapq.heappush(heap, (w[v], v))
		res = []
		for _ in range(len(heap)):
			(_, v) = heapq.heappop(heap)
			res.append(v)
		return res


class Solution:

	def watchedVideosByFriends(self, watchedVideos: List[List[str]], friends: List[List[int]], id: int, level: int) -> List[str]:
		vis = {id}
		q = deque()
		q.append(id)
		while q and level:
			ln = len(q)
			for _ in range(ln):
				x = q.popleft()
				for i in friends[x]:
					if i not in vis:
						q.append(i)
						vis.add(i)
			level -= 1
		d = defaultdict(int)
		for i in q:
			for j in watchedVideos[i]:
				d[j] += 1
		pq = []
		res = []
		for i in d:
			heapq.heappush(pq, (d[i], i))
		while pq:
			res.append(heapq.heappop(pq)[1])
		return res