Table: Listens
+-------------+---------+ | Column Name | Type | +-------------+---------+ | user_id | int | | song_id | int | | day | date | +-------------+---------+ This table may contain duplicates (In other words, there is no primary key for this table in SQL). Each row of this table indicates that the user user_id listened to the song song_id on the day day.
Table: Friendship
+---------------+---------+ | Column Name | Type | +---------------+---------+ | user1_id | int | | user2_id | int | +---------------+---------+ In SQL,(user1_id, user2_id) is the primary key for this table. Each row of this table indicates that the users user1_id and user2_id are friends. Note that user1_id < user2_id.
Recommend friends to Leetcodify users. We recommend user x to user y if:
x and y are not friends, andx and y listened to the same three or more different songs on the same day.Note that friend recommendations are unidirectional, meaning if user x and user y should be recommended to each other, the result table should have both user x recommended to user y and user y recommended to user x. Also, note that the result table should not contain duplicates (i.e., user y should not be recommended to user x multiple times.).
Return the result table in any order.
The result format is in the following example.
Example 1:
Input: Listens table: +---------+---------+------------+ | user_id | song_id | day | +---------+---------+------------+ | 1 | 10 | 2021-03-15 | | 1 | 11 | 2021-03-15 | | 1 | 12 | 2021-03-15 | | 2 | 10 | 2021-03-15 | | 2 | 11 | 2021-03-15 | | 2 | 12 | 2021-03-15 | | 3 | 10 | 2021-03-15 | | 3 | 11 | 2021-03-15 | | 3 | 12 | 2021-03-15 | | 4 | 10 | 2021-03-15 | | 4 | 11 | 2021-03-15 | | 4 | 13 | 2021-03-15 | | 5 | 10 | 2021-03-16 | | 5 | 11 | 2021-03-16 | | 5 | 12 | 2021-03-16 | +---------+---------+------------+ Friendship table: +----------+----------+ | user1_id | user2_id | +----------+----------+ | 1 | 2 | +----------+----------+ Output: +---------+----------------+ | user_id | recommended_id | +---------+----------------+ | 1 | 3 | | 2 | 3 | | 3 | 1 | | 3 | 2 | +---------+----------------+ Explanation: Users 1 and 2 listened to songs 10, 11, and 12 on the same day, but they are already friends. Users 1 and 3 listened to songs 10, 11, and 12 on the same day. Since they are not friends, we recommend them to each other. Users 1 and 4 did not listen to the same three songs. Users 1 and 5 listened to songs 10, 11, and 12, but on different days. Similarly, we can see that users 2 and 3 listened to songs 10, 11, and 12 on the same day and are not friends, so we recommend them to each other.
Problem Overview: You have listening activity from a music platform and a friendship graph between users. The task is to recommend songs to a user when multiple friends listened to the same song on the same day, while ensuring the user has not already listened to that song that day.
Approach 1: Friendship Expansion + Listening Join (SQL Aggregation) (Time: O(n log n), Space: O(n))
The core idea is to combine the friendship relationships with listening activity and count how many friends listened to the same song_id on a specific day. Start by normalizing the friendship table so every relationship appears in both directions (user → friend and friend → user). Join this expanded friendship set with the Listens table to fetch songs played by friends. Then group by user_id, song_id, and day and count distinct friends who listened to that song. If the count reaches the required threshold (for example, three friends), the song becomes a candidate recommendation.
Next, filter out songs the user already listened to on that same day. This is typically done with a LEFT JOIN or NOT EXISTS check against the user's own listening records. The result contains the recommended song_id for each user and day based on collective friend activity.
This approach relies heavily on relational operations: self-expanding friendships, joining activity logs, and using GROUP BY with COUNT(DISTINCT ...). SQL engines handle these operations efficiently when indexes exist on user_id, song_id, and day. Problems like this are classic relational analytics tasks and appear frequently when practicing database queries involving SQL joins and aggregation.
Recommended for interviews: The aggregation-based SQL approach is the expected solution. Interviewers want to see that you can expand bidirectional friendships, join behavioral data, and filter results using grouping and exclusion logic. A brute-force comparison of every user against every friend would be inefficient and difficult to express in SQL, while the join + aggregation strategy shows strong relational query design.
MySQL
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Friend Comparison | O(F × L) | O(1) | Conceptual baseline; rarely used in SQL because it scales poorly with large listening logs. |
| Friendship Expansion + Join + Aggregation | O(n log n) | O(n) | Best general solution. Uses joins and GROUP BY to count friend listens efficiently. |
| Join with NOT EXISTS Filtering | O(n log n) | O(n) | Preferred when explicitly excluding songs already listened to by the user. |
Leetcode HARD 1917 - Leetcodify Friends Recommendations: Explained by Everyday Data Science • Everyday Data Science • 800 views views
Practice Leetcodify Friends Recommendations with our built-in code editor and test cases.
Practice on FleetCode