Problem Description

The Second Degree Follower problem involves a directed graph representing a social network, where each node is a user and each directed edge means one user follows another. You are given a list of pairs edges where each pair [a, b] means user a follows user b. Given a target user x, you are asked to find all users who are second degree followers of x—that is, users who follow someone that x follows, but do not directly follow x and are not x themselves.

• Return the list of second degree followers in any order.
• Do not include users who directly follow x or x themselves.
• Each edge is unique (no duplicates).
• Assume user IDs are integers.

Thought Process

At first glance, the problem seems to require examining all possible two-step paths starting from x. A brute-force solution might check every pair of edges to see if there is a chain x → y → z, but this is inefficient for large graphs.

We need to:

• Find all users y whom x follows (first degree).
• For each y, find all users z whom y follows (potential second degree followers).
• Exclude x and any user who is already a direct follower of x.

Solution Approach

Let's break down the steps to efficiently solve the problem:

1. Build a following map: For each user, keep a set of users they follow. This helps us quickly find all users followed by a given user.
2. Identify first degree followers: Get the set of users that x follows directly.
3. Find second degree followers: For each user y that x follows, get the users y follows and add them to a result set.
4. Remove direct followers and x: To ensure we only include true second degree followers, remove x and any user already directly followed by x from the result set.
5. Return the result: Convert the set to a list and return.

We use sets for:

• Efficient duplicate elimination.
• Fast membership testing (O(1) time per check).

Example Walkthrough

Example Input:
edges = [[1,2], [2,3], [2,4], [3,5], [4,5], [1,6], [6,7]]
x = 1

1. Build following map:
   1 → {2, 6}
2 → {3, 4}
3 → {5}
4 → {5}
6 → {7}
2. First degree followers of 1: {2, 6}
3. Second degree candidates:
   • User 2 follows {3, 4} → add 3 and 4
   • User 6 follows {7} → add 7
   Result set is {3, 4, 7}
4. Remove direct followers and 1:
   • Remove 1 (not in set)
   • Remove 2 and 6 (not in set)
   Final answer: [3, 4, 7]

Code Implementation

def second_degree_followers(edges, x):
    from collections import defaultdict

    # Build following map
    following = defaultdict(set)
    for a, b in edges:
        following[a].add(b)

    # First degree followers
    first_deg = following.get(x, set())

    # Second degree followers (excluding direct and self)
    second_deg = set()
    for y in first_deg:
        second_deg.update(following.get(y, set()))

    # Remove direct followers and self
    second_deg -= first_deg
    second_deg.discard(x)

    return list(second_deg)
      

#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

vector<int> secondDegreeFollowers(vector<vector<int>>& edges, int x) {
    unordered_map<int, unordered_set<int>> following;
    for (const auto& e : edges) {
        following[e[0]].insert(e[1]);
    }
    unordered_set<int> firstDeg = following[x];
    unordered_set<int> secondDeg;
    for (int y : firstDeg) {
        if (following.count(y)) {
            for (int z : following[y]) {
                secondDeg.insert(z);
            }
        }
    }
    for (int y : firstDeg) {
        secondDeg.erase(y);
    }
    secondDeg.erase(x);
    return vector<int>(secondDeg.begin(), secondDeg.end());
}
      

import java.util.*;

public class Solution {
    public List<Integer> secondDegreeFollowers(int[][] edges, int x) {
        Map<Integer, Set<Integer>> following = new HashMap<>();
        for (int[] e : edges) {
            following.computeIfAbsent(e[0], k -> new HashSet<>()).add(e[1]);
        }
        Set<Integer> firstDeg = following.getOrDefault(x, new HashSet<>());
        Set<Integer> secondDeg = new HashSet<>();
        for (int y : firstDeg) {
            Set<Integer> next = following.getOrDefault(y, Collections.emptySet());
            secondDeg.addAll(next);
        }
        secondDeg.removeAll(firstDeg);
        secondDeg.remove(x);
        return new ArrayList<>(secondDeg);
    }
}
      

function secondDegreeFollowers(edges, x) {
    const following = new Map();
    for (const [a, b] of edges) {
        if (!following.has(a)) following.set(a, new Set());
        following.get(a).add(b);
    }
    const firstDeg = following.get(x) || new Set();
    const secondDeg = new Set();
    for (const y of firstDeg) {
        if (following.has(y)) {
            for (const z of following.get(y)) {
                secondDeg.add(z);
            }
        }
    }
    for (const y of firstDeg) {
        secondDeg.delete(y);
    }
    secondDeg.delete(x);
    return Array.from(secondDeg);
}
      

Time and Space Complexity

• Brute-force approach:
  For each user y that x follows, check every edge to see if y follows someone else. This is O(E * D), where E is the number of edges and D is the out-degree of x.
• Optimized approach:
  
  • Time Complexity: O(E), since we process each edge once to build the map, and then for each first degree follower, we process their out-edges (which in total is at most E).
  • Space Complexity: O(E), for storing the following map and result sets.

The optimized solution is efficient and scales well for large input sizes.

Summary

The Second Degree Follower problem is a classic example of graph traversal and set manipulation. By representing the follower relationships as adjacency lists and using sets for efficient lookups and duplicate elimination, we can quickly find all users who are two steps away in the follower graph, while filtering out direct followers and the user themselves. This approach is both elegant and efficient, leveraging basic data structures to solve a real-world network problem.