Find Similar Communities

Problem

We have communities C1, C2, ... and followers F1, F2, .... Each follower may follow any number of communities. Two communities are directly related if they share at least one follower. Given a community Cx, return all communities directly related to Cx (excluding Cx itself).

Follow-up: extend the function to accept a non-negative integer degree and return all communities that are related to Cx within degree steps (i.e., all communities at distance ≤ degree in the community graph where edges connect communities that share followers).

Example

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


Community -> followers:
C1: [F1, F3]
C2: [F1, F2]
C3: [F2]
C4: [F3]

Follower -> communities:
F1: [C1, C2]
F2: [C2, C3]
F3: [C1, C4]

get_related_communities(C4) -> [C1]
get_related_communities(C2) -> [C1, C3]

get_related_communities_with_degree(C4, 1) -> [C1]
get_related_communities_with_degree(C4, 2) -> [C1, C2]

Solution

We give two clean methods: Method 1 finds direct neighbors using the follower→communities mapping; Method 2 performs a BFS over the implicit community graph to collect related communities up to a given degree.

Method 1 — Direct neighbors (one-hop)

Intuition

For a community c, iterate its followers and gather all communities followed by those followers. Remove c itself from the result.

Approach

Look up the list F = followers(c) (from communityMap).
For each f in F, add every community in followerMap[f] to a result set ans.
Remove c from ans if present and return the set (or list).

Edge cases: if c is unknown return an empty set.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution {
 public:
	// communityMap: community -> list of followers
	// followerMap: follower -> list of communities
	std::vector<std::string> getRelated(const std::string& c,
																			const std::unordered_map<std::string, std::vector<std::string>>& communityMap,
																			const std::unordered_map<std::string, std::vector<std::string>>& followerMap) {
		if (!communityMap.count(c)) return {};
		std::unordered_set<std::string> ans;
		for (const auto& f : communityMap.at(c)) {
			if (!followerMap.count(f)) continue;
			for (const auto& comm : followerMap.at(f)) ans.insert(comm);
		}
		ans.erase(c);
		return std::vector<std::string>(ans.begin(), ans.end());
	}
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


package main

func getRelated(c string, communityMap map[string][]string, followerMap map[string][]string) []string {
		followers, ok := communityMap[c]
		if !ok { return []string{} }
		set := make(map[string]struct{})
		for _, f := range followers {
				for _, comm := range followerMap[f] {
						set[comm] = struct{}{}
				}
		}
		delete(set, c)
		out := make([]string, 0, len(set))
		for k := range set { out = append(out, k) }
		return out
}

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


class Solution {
	public List<String> getRelated(String c, Map<String, List<String>> communityMap, Map<String, List<String>> followerMap) {
		if (!communityMap.containsKey(c)) return Collections.emptyList();
		Set<String> ans = new HashSet<>();
		for (String f : communityMap.get(c)) {
			List<String> comms = followerMap.get(f);
			if (comms == null) continue;
			ans.addAll(comms);
		}
		ans.remove(c);
		return new ArrayList<>(ans);
	}
}

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


from typing import List, Dict

class Solution:
		def get_related(self, c: str, community_map: Dict[str, List[str]], follower_map: Dict[str, List[str]]) -> List[str]:
				if c not in community_map:
						return []
				ans = set()
				for f in community_map[c]:
						for comm in follower_map.get(f, []):
								ans.add(comm)
				ans.discard(c)
				return list(ans)

Complexity

⏰ Time complexity: O(F * K) where F = number of followers of c and K = average communities per follower. We inspect each follower once and each community listed for that follower.
🧺 Space complexity: O(R) where R is the number of related communities returned (the result set).

Method 2 — BFS over community graph (degrees)

Intuition

Treat communities as nodes in a graph where an undirected edge connects two communities that share at least one follower. Starting from c, perform BFS up to degree levels and collect all visited nodes (excluding c). We can obtain neighbors on demand using get_related (Method 1) or precompute adjacency if many queries are expected.

Approach

If degree == 0 return an empty set.
Initialize visited = {c} and a queue q with c.
For level from 1..degree:
- For each node currently in q, fetch its neighbors via get_related(node) and add unvisited neighbors to next_q and visited.
- Replace q with next_q.
Return visited - {c} as the related communities up to degree.

Edge cases: unknown c returns empty. For repeated queries, precomputing adjacency (community_graph) speeds up repeated BFS runs.

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


class Solution {
 public:
	vector<string> relatedWithDegree(const string& c, int degree,
																	 const unordered_map<string, vector<string>>& communityMap,
																	 const unordered_map<string, vector<string>>& followerMap) {
		if (degree <= 0 || !communityMap.count(c)) return {};
		unordered_set<string> visited; visited.insert(c);
		queue<string> q; q.push(c);
		for (int d = 0; d < degree && !q.empty(); ++d) {
			int sz = q.size();
			for (int i = 0; i < sz; ++i) {
				string cur = q.front(); q.pop();
				// get neighbors on the fly
				for (const auto& f : communityMap.at(cur)) {
					if (!followerMap.count(f)) continue;
					for (const auto& nb : followerMap.at(f)) {
						if (!visited.count(nb)) { visited.insert(nb); q.push(nb); }
					}
				}
			}
		}
		visited.erase(c);
		return vector<string>(visited.begin(), visited.end());
	}
};

 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


package main

func relatedWithDegree(c string, degree int, communityMap map[string][]string, followerMap map[string][]string) []string {
		if degree <= 0 { return []string{} }
		if _, ok := communityMap[c]; !ok { return []string{} }
		visited := make(map[string]struct{})
		visited[c] = struct{}{}
		q := []string{c}
		for d := 0; d < degree && len(q) > 0; d++ {
				next := []string{}
				for _, cur := range q {
						for _, f := range communityMap[cur] {
								for _, nb := range followerMap[f] {
										if _, ok := visited[nb]; !ok {
												visited[nb] = struct{}{}
												next = append(next, nb)
										}
								}
						}
				}
				q = next
		}
		delete(visited, c)
		out := make([]string, 0, len(visited))
		for k := range visited { out = append(out, k) }
		return out
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution {
	public List<String> relatedWithDegree(String c, int degree, Map<String, List<String>> communityMap, Map<String, List<String>> followerMap) {
		if (degree <= 0 || !communityMap.containsKey(c)) return Collections.emptyList();
		Set<String> visited = new HashSet<>(); visited.add(c);
		Queue<String> q = new LinkedList<>(); q.add(c);
		for (int d = 0; d < degree && !q.isEmpty(); ++d) {
			int sz = q.size();
			for (int i = 0; i < sz; ++i) {
				String cur = q.poll();
				for (String f : communityMap.get(cur)) {
					List<String> nbs = followerMap.get(f);
					if (nbs == null) continue;
					for (String nb : nbs) {
						if (visited.add(nb)) q.add(nb);
					}
				}
			}
		}
		visited.remove(c);
		return new ArrayList<>(visited);
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


from typing import List, Dict
from collections import deque

class Solution:
		def related_with_degree(self, c: str, degree: int, community_map: Dict[str, List[str]], follower_map: Dict[str, List[str]]) -> List[str]:
				if degree <= 0 or c not in community_map:
						return []
				visited = {c}
				q = deque([c])
				for _ in range(degree):
						for _ in range(len(q)):
								cur = q.popleft()
								for f in community_map[cur]:
										for nb in follower_map.get(f, []):
												if nb not in visited:
														visited.add(nb)
														q.append(nb)
				visited.discard(c)
				return list(visited)

Complexity

⏰ Time complexity: O(D * F * K) where D = degree, F = average followers inspected per visited community, and K = average communities per follower. In the worst case this can approach O(V + E) of the implicit community graph visited up to that radius.
🧺 Space complexity: O(V) for the visited set (number of communities reached).

Notes

If you plan to run many queries, precomputing the community adjacency list (graph) from followerMap is recommended: iterate each follower and connect all pairs of communities it follows — this costs O(sum_f c_f^2) where c_f is communities followed by follower f.
The implementations above use get_related on the fly; replace it with a precomputed adjacency map for faster repeated queries.

Problem#

Example#

Solution#

Method 1 — Direct neighbors (one-hop)#

Intuition#

Approach#

Code#

Complexity#

Method 2 — BFS over community graph (degrees)#

Intuition#

Approach#

Code#

Complexity#

Notes#

Problem

Example

Solution

Method 1 — Direct neighbors (one-hop)

Intuition

Approach

Code

Complexity

Method 2 — BFS over community graph (degrees)

Intuition

Approach

Code

Complexity

Notes