Watch 7 video solutions for Number of Calls Between Two Persons, a medium level problem involving Database. This walkthrough by Everyday Data Science has 6,152 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Table: Calls
+-------------+---------+ | Column Name | Type | +-------------+---------+ | from_id | int | | to_id | int | | duration | int | +-------------+---------+ This table does not have a primary key (column with unique values), it may contain duplicates. This table contains the duration of a phone call between from_id and to_id. from_id != to_id
Write a solution to report the number of calls and the total call duration between each pair of distinct persons (person1, person2) where person1 < person2.
Return the result table in any order.
The result format is in the following example.
Example 1:
Input: Calls table: +---------+-------+----------+ | from_id | to_id | duration | +---------+-------+----------+ | 1 | 2 | 59 | | 2 | 1 | 11 | | 1 | 3 | 20 | | 3 | 4 | 100 | | 3 | 4 | 200 | | 3 | 4 | 200 | | 4 | 3 | 499 | +---------+-------+----------+ Output: +---------+---------+------------+----------------+ | person1 | person2 | call_count | total_duration | +---------+---------+------------+----------------+ | 1 | 2 | 2 | 70 | | 1 | 3 | 1 | 20 | | 3 | 4 | 4 | 999 | +---------+---------+------------+----------------+ Explanation: Users 1 and 2 had 2 calls and the total duration is 70 (59 + 11). Users 1 and 3 had 1 call and the total duration is 20. Users 3 and 4 had 4 calls and the total duration is 999 (100 + 200 + 200 + 499).
Problem Overview: You are given a Calls table containing from_id, to_id, and duration. Each row represents a phone call between two people. The task is to compute the total number of calls and total call duration for every unique pair of people, regardless of who initiated the call.
The tricky part is that calls are directional in the table. A call from 1 → 2 and another from 2 → 1 belong to the same pair. The result must normalize the pair so each combination appears only once.
Approach 1: Pair Normalization with Grouping and Summing (O(n log n) time, O(n) space)
The cleanest solution normalizes each pair before aggregation. For every row, compute the smaller user ID as person1 and the larger as person2. In MySQL, this is done using LEAST(from_id, to_id) and GREATEST(from_id, to_id). This ensures calls like (1,2) and (2,1) map to the same canonical pair.
After normalizing the pair, aggregate the rows using GROUP BY. Use COUNT(*) to compute the number of calls between the two people and SUM(duration) to calculate the total duration. The database engine scans the table once, computes normalized pairs, and groups them together.
The time complexity is roughly O(n log n) due to grouping operations performed by the SQL engine (often implemented with sorting or hashing). Space complexity is O(n) for intermediate aggregation results. This approach is concise, readable, and efficient for large datasets.
This pattern—normalizing symmetric relationships before aggregation—appears frequently in database and SQL interview questions. Whenever relationships are bidirectional, converting them into a consistent order simplifies grouping logic.
In practice, the query follows three clear steps: normalize the pair with LEAST/GREATEST, aggregate with COUNT and SUM, and group using GROUP BY. The database engine handles the heavy lifting, making this approach both performant and easy to reason about.
Recommended for interviews: The grouping approach with LEAST and GREATEST is the expected solution. It demonstrates that you understand symmetric relationships and SQL aggregation patterns such as GROUP BY. A brute-force restructuring of pairs or multiple queries would work but adds unnecessary complexity. Interviewers look for the normalization insight because it keeps the query simple and scalable.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Pair Normalization with LEAST/GREATEST + GROUP BY | O(n log n) | O(n) | Best general solution for SQL databases; cleanly handles bidirectional relationships |
| Conditional CASE Pair Ordering + GROUP BY | O(n log n) | O(n) | Useful when LEAST/GREATEST functions are unavailable in the SQL dialect |
| Self-Join to Merge Bidirectional Calls | O(n^2) | O(n) | Conceptual approach for understanding relationships but inefficient for large tables |
