LeetCode 614: Second Degree Follower Solution in Python – A Step-by-Step Guide

What Is LeetCode 614: Second Degree Follower?

In LeetCode 614: Second Degree Follower, you’re given a table follow with columns followee (the user being followed) and follower (the user following them). Your task is to find all users who are second-degree followers—those who follow at least one person (a "middle" user) who follows someone else (a "leader") that the original user also follows—and return each such follower along with their count of such middle users. For example, if A follows B and C, and B follows C, A is a second-degree follower of C via B. This problem tests your ability to analyze multi-level relationships, typically posed as an SQL query with self-joins, but we’ll solve it in Python for a coding twist.

Problem Statement

• Input: A list of records (or table rows) with [followee, follower].
• Output: A list of [follower, num] where follower is a second-degree follower and num is the count of their middle users.
• Rules:
• Second-degree follower: User A follows B, B follows C, and A follows C.
• Count unique middle users (B) per follower (A).
• Return only followers with at least one such middle user.

Constraints

• Table has at least 1 row.
• followee and follower are integers (user IDs).
• Number of rows ≤ 1000.
• Each user follows distinct users (no duplicate followee-follower pairs).

Examples

• Input:
``` followee | follower 1 | 2 2 | 3 1 | 3 ```
• Output:
``` [3, 1] # 3 follows 2, 2 follows 1, 3 follows 1; 1 middle (2) ```
• Input:
``` followee | follower 1 | 2 1 | 3 2 | 4 3 | 4 ```
• Output:
``` [4, 2] # 4 follows 2 (2->1, 4->1), 4 follows 3 (3->1, 4->1); 2 middles (2, 3) ```

These examples show the connections—let’s solve it!

Understanding the Problem: Tracing Second-Degree Followers

To solve LeetCode 614: Second Degree Follower in Python, we need to identify users (followers) who have a chain of follow relationships like A → B → C where A also follows C, then count the unique B’s for each A. A brute-force approach might check every triple, but we can optimize with data structures. We’ll use:

• Best Solution (Set-Based Follower Counting): O(n²) time, O(n) space—fast and clean.
• Alternative Solution (Dictionary-Based Mapping): O(n²) time, O(n²) space—detailed but heavier.

Let’s start with the set-based solution, breaking it down for beginners.

Best Solution: Set-Based Follower Counting

Why This Is the Best Solution

The set-based approach is the top choice for LeetCode 614 because it’s efficient—O(n²) time with O(n) space—and uses sets to quickly track followees and followers, mimicking SQL joins in a Python-friendly way. It avoids redundant storage and scales well within constraints (≤ 1000 rows). It’s like building a quick lookup table to spot second-degree chains!

How It Works

Think of this as mapping a social web:

• Step 1: Build Follower Sets:
• Create a set of followees for each follower.
• Create a set of followers for each followee.
• Step 2: Identify Second-Degree Followers:
• For each follower A:
• Check each followee B of A.
• For each followee C of B, if A follows C, B is a middle user.
• Step 3: Count Middle Users:
• Use a set to count unique middle users per follower.
• Step 4: Return Result:
• List [follower, num] for valid second-degree followers.

It’s like tracing follow chains with a checklist!

Step-by-Step Example

Example:

Copy codefollowee | follower
1        | 2
2        | 3
1        | 3

• Step 1: Build sets:
• Followees: {2: {1}, 3: {1, 2}}.
• Followers: {1: {2, 3}, 2: {3}}.
• Step 2: Check follower 3:
• 3 follows 1:
• 1’s followers: {2, 3}.
• 3 follows 2 (in 1’s followers), middle = {2}.
• 3 follows 2:
• 2’s followers: {3}.
• 3 follows 1 (not in 2’s followers), no add.
• Step 3: Count for 3: 1 middle (2).
• Output: [[3, 1]].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codefrom collections import defaultdict

class Solution:
    def secondDegreeFollower(self, follow: List[List[int]]) -> List[List]:
        # Step 1: Build followee and follower sets
        followees = defaultdict(set)  # follower -> set of followees
        followers = defaultdict(set)  # followee -> set of followers

        for followee, follower in follow:
            followees[follower].add(followee)
            followers[followee].add(follower)

        # Step 2: Find second-degree followers
        result = []
        for follower in followees:
            middle_users = set()
            # Check each followee of this follower
            for b in followees[follower]:
                # Check each followee of b
                for c in followers[b]:
                    if c in followees[follower] and c != follower:
                        middle_users.add(b)
            if middle_users:  # If any middle users found
                result.append([follower, len(middle_users)])

        # Step 3: Return result
        return result

• Line 1: Import defaultdict for ease.
• Lines 6-10: Build sets:
• followees: Who each follower follows.
• followers: Who follows each followee.
• Lines 13-22: Process:
• For each follower, track middle users.
• Check B’s followers (C) against A’s followees.
• Add B if C is followed by A.
• Time Complexity: O(n²)—nested loops over followers.
• Space Complexity: O(n)—sets store follow relationships.

This is like a social chain tracker—fast and tidy!

Alternative Solution: Dictionary-Based Mapping with Explicit Joins

Why an Alternative Approach?

The dictionary-based approach maps all relationships explicitly—O(n²) time, O(n²) space. It’s more detailed, building a full graph of follow chains, but uses more memory and is less efficient. It’s like keeping a complete ledger of every connection!

How It Works

Picture this as a detailed social map:

• Step 1: Map followers to followees and vice versa.
• Step 2: Build second-degree connections:
• For each A → B, add B’s followees (C) if A follows C.
• Step 3: Count middle users per follower.
• Step 4: Return results with counts.

It’s like a thorough network audit!

Step-by-Step Example

Example:

Copy codefollowee | follower
1        | 2
2        | 3
1        | 3

• Step 1: Maps:
• followees = {2: {1}, 3: {1, 2}}.
• followers = {1: {2, 3}, 2: {3}}.
• Step 2: Second-degree:
• 3: For 1, 1’s followers = {2, 3}, 3 follows 2, add 2.
• 3: For 2, 2’s followers = {3}, no match with 1.
• Middle for 3: {2}.
• Step 3: Count: 3 has 1 middle.
• Output: [[3, 1]].

Code for Dictionary Approach

Copy codefrom collections import defaultdict

class Solution:
    def secondDegreeFollower(self, follow: List[List[int]]) -> List[List]:
        # Step 1: Build maps
        followees = defaultdict(set)
        followers = defaultdict(set)
        for followee, follower in follow:
            followees[follower].add(followee)
            followers[followee].add(follower)

        # Step 2: Build second-degree map
        second_degree = defaultdict(set)
        for follower in followees:
            for b in followees[follower]:  # Middle user
                for c in followers[b]:     # Leader
                    if c in followees[follower] and c != follower:
                        second_degree[follower].add(b)

        # Step 3: Format result
        result = [[follower, len(middles)] for follower, middles in second_degree.items()]
        return result

• Lines 6-10: Build followee/follower maps.
• Lines 13-17: Map second-degree middles.
• Line 20: Convert to [follower, num].
• Time Complexity: O(n²)—nested loops.
• Space Complexity: O(n²)—stores all chains.

It’s a full social trace—clear but heavy!

Comparing the Two Solutions

• Set-Based (Best):
• Pros: O(n²) time, O(n) space, efficient and clean.
• Cons: Less explicit.
• Dictionary (Alternative):
• Pros: O(n²) time, O(n²) space, detailed and extensible.
• Cons: More memory.

Set-based wins for efficiency.

Additional Examples and Edge Cases

• Input: [[1,2]]
• Output: [] (No second-degree).
• Input: [[1,2], [2,3], [3,1]]
• Output: [] (Cycle, no match).

Both handle these well.

Complexity Breakdown

• Set-Based: Time O(n²), Space O(n).
• Dictionary: Time O(n²), Space O(n²).

Set-based is optimal.

Key Takeaways

• Set-Based: Quick chains—smart!
• Dictionary: Full map—clear!
• Graphs: Relationships are fun.
• Python Tip: Sets rule—see Python Basics.

Final Thoughts: Find Those Followers

LeetCode 614: Second Degree Follower in Python is a cool social network puzzle. Set-based counting offers speed and simplicity, while dictionary mapping gives a detailed view. Want more? Try LeetCode 547: Number of Provinces or LeetCode 261: Graph Valid Tree. Ready to trace? Head to Solve LeetCode 614 on LeetCode and spot those second-degree followers today!