All the Pairs With the Maximum Number of Common Followers - Solution & Explanation

Problem Overview: The Relations table stores which follower_id follows which user_id. The task is to find every pair of users who share the largest number of common followers. If multiple pairs have the same maximum count, return all of them.

Approach 1: Self Join + GROUP BY Aggregation (O(n²) time, O(n) space)

The core idea is to compare users who share the same follower. Perform a self join on the Relations table using follower_id so rows with the same follower are paired together. Enforce r1.user_id < r2.user_id to avoid duplicate and reversed pairs. Each joined row represents one common follower for a pair of users. Use GROUP BY on the pair and count rows to compute the number of shared followers. After computing counts for every pair, filter only those whose count equals the global maximum.

This pattern is common in SQL interview problems where relationships must be compared within the same table. The heavy lifting happens in the join and aggregation step.

Approach 2: Self Join + Window Function Ranking (O(n²) time, O(n) space)

Another clean implementation uses the same self join but replaces the separate max calculation with a window function. After grouping pairs and counting shared followers, apply MAX(cnt) OVER() or a ranking window such as DENSE_RANK(). This computes the global maximum in the same result set. Then filter rows where the count equals that maximum. The logic stays compact and avoids an extra subquery.

This approach relies on features commonly used in SQL joins and analytical queries. It is easier to extend if you later need the top k pairs instead of only the maximum.

Approach 3: Self Join + Subquery Max Filter (O(n²) time, O(n) space)

First compute the number of common followers for each pair using the self join and GROUP BY. Store this intermediate result in a derived table. A nested subquery calculates MAX(common_count) from that result. Finally, return only rows where the pair's count equals that maximum value. This is the most common MySQL implementation because it is straightforward and works without window functions.

The approach highlights two fundamental SQL techniques: relational comparison through self joins and aggregation using GROUP BY.

Recommended for interviews: The self join with GROUP BY and a max filter is the expected solution. It demonstrates that you understand relational joins, deduplication with user_id < user_id, and aggregation logic. A brute-force mindset—comparing every user pair—shows the intuition, but expressing it efficiently in SQL using joins and grouping is what interviewers want to see.