Solution Explanation for LeetCode 1699: Number of Calls Between Two Persons

This problem requires analyzing a Calls table to determine the number of calls and total call duration between each unique pair of individuals. The solution involves grouping and aggregation.

Approach:

The core idea is to:

1. Normalize the IDs: Since a call can be represented as (from_id, to_id) or (to_id, from_id), we need to consistently represent each call pair. We achieve this by defining person1 as the smaller ID and person2 as the larger ID. This ensures that pairs (1,2) and (2,1) are treated as the same. We can use either IF statements or the LEAST and GREATEST functions in SQL to accomplish this.

2. Group and Aggregate: After normalizing the IDs, we group the results by person1 and person2. This allows us to count the number of calls (call_count) and sum the total duration (total_duration) for each unique pair.

SQL Solutions:

Two equivalent SQL solutions are presented below using different methods for normalizing the IDs. Both solutions have the same time and space complexity.

Solution 1 (using IF):

SELECT
    IF(from_id < to_id, from_id, to_id) AS person1,
    IF(from_id < to_id, to_id, from_id) AS person2,
    COUNT(*) AS call_count,
    SUM(duration) AS total_duration
FROM Calls
GROUP BY person1, person2;

This solution uses IF statements to assign the smaller ID to person1 and the larger ID to person2. COUNT(*) counts the rows in each group, and SUM(duration) calculates the sum of durations.

Solution 2 (using LEAST and GREATEST):

SELECT
    LEAST(from_id, to_id) AS person1,
    GREATEST(from_id, to_id) AS person2,
    COUNT(*) AS call_count,
    SUM(duration) AS total_duration
FROM Calls
GROUP BY person1, person2;

This solution achieves the same result using the built-in LEAST and GREATEST functions, which are more concise and often preferred for readability.

Time and Space Complexity:

• Time Complexity: O(N log N), where N is the number of rows in the Calls table. The dominant operation is the GROUP BY clause, which involves sorting or hashing the rows to group them. The specific time complexity depends on the database engine's implementation of GROUP BY.

• Space Complexity: O(M), where M is the number of unique pairs of (person1, person2). This space is needed to store the intermediate results during the grouping and aggregation process. In the worst case, M could be O(N^2), but this is unlikely unless the data has a very specific pattern. Generally, M will be significantly smaller than N.

Note: The actual execution time and space usage will depend on factors like the database system, the size of the Calls table, and the available resources (e.g., memory, CPU). The complexity analysis provides an estimate of the scaling behavior as the input size grows.