Skip to main content
Talentd

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

MediumPremiumFree on FleetCodeDatabase4 min readAsked at: Lime
Practice this problem

Problem Statement

Table: Relations

+-------------+------+
| Column Name | Type |
+-------------+------+
| user_id     | int  |
| follower_id | int  |
+-------------+------+
(user_id, follower_id) is the primary key (combination of columns with unique values) for this table.
Each row of this table indicates that the user with ID follower_id is following the user with ID user_id.

 

Write a solution to find all the pairs of users with the maximum number of common followers. In other words, if the maximum number of common followers between any two users is maxCommon, then you have to return all pairs of users that have maxCommon common followers.

The result table should contain the pairs user1_id and user2_id where user1_id < user2_id.

Return the result table in any order.

The result format is in the following example.

 

Example 1:

Input: 
Relations table:
+---------+-------------+
| user_id | follower_id |
+---------+-------------+
| 1       | 3           |
| 2       | 3           |
| 7       | 3           |
| 1       | 4           |
| 2       | 4           |
| 7       | 4           |
| 1       | 5           |
| 2       | 6           |
| 7       | 5           |
+---------+-------------+
Output: 
+----------+----------+
| user1_id | user2_id |
+----------+----------+
| 1        | 7        |
+----------+----------+
Explanation: 
Users 1 and 2 have two common followers (3 and 4).
Users 1 and 7 have three common followers (3, 4, and 5).
Users 2 and 7 have two common followers (3 and 4).
Since the maximum number of common followers between any two users is 3, we return all pairs of users with three common followers, which is only the pair (1, 7). We return the pair as (1, 7), not as (7, 1).
Note that we do not have any information about the users that follow users 3, 4, and 5, so we consider them to have 0 followers.

Approach Overview

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.

Solution

Code

MySQL

MySQL

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Self Join + GROUP BYO(n²)O(n)Standard SQL solution; works in all relational databases
Self Join + Subquery Max FilterO(n²)O(n)Clean MySQL implementation when window functions are unnecessary
Self Join + Window FunctionO(n²)O(n)Modern SQL engines supporting analytic functions

Video Solution

INSTAGRAM LeetCode Medium “Pairs With Maximum Common Followers" 1951 Interview SQL Question | EDS • Everyday Data Science • 2,825 views views

Frequently Asked Questions

Is All the Pairs With the Maximum Number of Common Followers easy or hard?
The problem is rated Medium because it requires understanding SQL self joins and aggregation logic. The query itself is not long, but recognizing that common followers can be found by joining the table with itself on follower_id is the key insight.
All the Pairs With the Maximum Number of Common Followers Python/Java solution
This problem is designed for SQL rather than general-purpose programming languages. The standard solution is a MySQL query using a self join and GROUP BY to count shared followers. Python or Java would typically only be used to execute the SQL query against the database.
How to solve All the Pairs With the Maximum Number of Common Followers in O(n)?
Achieving strict O(n) time is generally not feasible because identifying common followers requires comparing relationships across users. SQL solutions rely on self joins, which conceptually examine combinations of rows with the same follower. Database indexing on follower_id can significantly improve practical performance even though the theoretical complexity remains higher.
What is the best approach for All the Pairs With the Maximum Number of Common Followers?
The best approach uses a self join on the Relations table by follower_id, followed by GROUP BY on user pairs. Each joined row represents a shared follower, and COUNT(*) gives the number of common followers. After computing counts for all pairs, filter the rows whose count equals the maximum value. This SQL pattern efficiently compares relationships within the same table.
Is All the Pairs With the Maximum Number of Common Followers asked at Google/Amazon/Meta?
Problems involving relationship analysis, follower graphs, and SQL self joins commonly appear in interviews at companies like Meta and Google. Social graph data naturally leads to queries that count shared connections. This problem reflects that pattern by asking for pairs of users with the most common followers.
What data structure is used in All the Pairs With the Maximum Number of Common Followers?
The solution relies on relational database operations rather than traditional in-memory data structures. The key techniques are SQL self joins, GROUP BY aggregation, and optional window functions. Conceptually, the join acts like comparing adjacency lists of followers between users.
What is the time complexity of All the Pairs With the Maximum Number of Common Followers?
The typical SQL solution using a self join runs in O(n²) time in the worst case because each row may be compared with other rows sharing the same follower. Aggregation with GROUP BY then processes the generated pairs. Space complexity is about O(n) for storing grouped results.

Ready to solve this problem?

Practice All the Pairs With the Maximum Number of Common Followers with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary