First and Last Call On the Same Day

Problem

Table: Calls

+--------------+----------+
| Column Name  | Type     |
+--------------+----------+
| caller_id    | int      |
| recipient_id | int      |
| call_time    | datetime |
+--------------+----------+
(caller_id, recipient_id, call_time) is the primary key (combination of columns with unique values) for this table.
Each row contains information about the time of a phone call between caller_id and recipient_id.

Write a solution to report the IDs of the users whose first and last calls on any day were with the same person. Calls are counted regardless of being the caller or the recipient.

Return the result table in any order.

The result format is in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


Input: 
Calls table:
+-----------+--------------+---------------------+
| caller_id | recipient_id | call_time           |
+-----------+--------------+---------------------+
| 8         | 4            | 2021-08-24 17:46:07 |
| 4         | 8            | 2021-08-24 19:57:13 |
| 5         | 1            | 2021-08-11 05:28:44 |
| 8         | 3            | 2021-08-17 04:04:15 |
| 11        | 3            | 2021-08-17 13:07:00 |
| 8         | 11           | 2021-08-17 22:22:22 |
+-----------+--------------+---------------------+
Output: 
+---------+
| user_id |
+---------+
| 1       |
| 4       |
| 5       |
| 8       |
+---------+
Explanation: 
On 2021-08-24, the first and last call of this day for user 8 was with user 4. User 8 should be included in the answer.
Similarly, user 4 on 2021-08-24 had their first and last call with user 8. User 4 should be included in the answer.
On 2021-08-11, user 1 and 5 had a call. This call was the only call for both of them on this day. Since this call is the first and last call of the day for both of them, they should both be included in the answer.

Solution

Method 1 – Self Join and Grouping

Intuition

For each user and each day, we want to check if their first and last call (regardless of being caller or recipient) were with the same person. We can treat all calls as undirected, find the first and last call per user per day, and compare the other party.

Approach

For each call, treat both caller and recipient as the user, and the other as the partner.
For each user and each day, collect all calls (as user, partner, date, time).
For each (user, date), find the earliest and latest call_time and the corresponding partner.
If the partner for the first and last call is the same, include the user.
Return the list of user IDs (distinct).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


WITH AllCalls AS (
  SELECT caller_id AS user_id, recipient_id AS partner_id, call_time FROM Calls
  UNION ALL
  SELECT recipient_id AS user_id, caller_id AS partner_id, call_time FROM Calls
),
CallInfo AS (
  SELECT user_id, partner_id, DATE(call_time) AS day, call_time,
         ROW_NUMBER() OVER (PARTITION BY user_id, DATE(call_time) ORDER BY call_time) AS rn_first,
         ROW_NUMBER() OVER (PARTITION BY user_id, DATE(call_time) ORDER BY call_time DESC) AS rn_last
  FROM AllCalls
)
SELECT DISTINCT user_id
FROM (
  SELECT user_id, day,
         MAX(CASE WHEN rn_first = 1 THEN partner_id END) AS first_partner,
         MAX(CASE WHEN rn_last = 1 THEN partner_id END) AS last_partner
  FROM CallInfo
  GROUP BY user_id, day
) t
WHERE first_partner = last_partner;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


WITH AllCalls AS (
  SELECT caller_id AS user_id, recipient_id AS partner_id, call_time FROM Calls
  UNION ALL
  SELECT recipient_id AS user_id, caller_id AS partner_id, call_time FROM Calls
),
CallInfo AS (
  SELECT user_id, partner_id, call_time::date AS day, call_time,
         ROW_NUMBER() OVER (PARTITION BY user_id, call_time::date ORDER BY call_time) AS rn_first,
         ROW_NUMBER() OVER (PARTITION BY user_id, call_time::date ORDER BY call_time DESC) AS rn_last
  FROM AllCalls
)
SELECT DISTINCT user_id
FROM (
  SELECT user_id, day,
         MAX(CASE WHEN rn_first = 1 THEN partner_id END) AS first_partner,
         MAX(CASE WHEN rn_last = 1 THEN partner_id END) AS last_partner
  FROM CallInfo
  GROUP BY user_id, day
) t
WHERE first_partner = last_partner;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def first_last_same_partner(self, Calls: 'pd.DataFrame') -> 'pd.DataFrame':
        import pandas as pd
        df1 = Calls[['caller_id', 'recipient_id', 'call_time']].copy()
        df2 = Calls[['recipient_id', 'caller_id', 'call_time']].copy()
        df1.columns = ['user_id', 'partner_id', 'call_time']
        df2.columns = ['user_id', 'partner_id', 'call_time']
        all_calls = pd.concat([df1, df2], ignore_index=True)
        all_calls['day'] = pd.to_datetime(all_calls['call_time']).dt.date
        res = all_calls.sort_values('call_time').groupby(['user_id', 'day'])
        first = res.first().reset_index()
        last = res.last().reset_index()
        merged = pd.merge(first, last, on=['user_id', 'day'], suffixes=('_first', '_last'))
        ans = merged[merged['partner_id_first'] == merged['partner_id_last']]['user_id'].drop_duplicates().to_frame()
        return ans

Complexity

⏰ Time complexity: O(N log N), where N is the number of calls, due to sorting and grouping.
🧺 Space complexity: O(N), for storing all calls and intermediate results.

Problem#

Examples#

Solution#

Method 1 – Self Join and Grouping#

Intuition#

Approach#

Code#

Complexity#