LeetCode 1972 - First and Last Call On the Same Day

The problem provides a table of phone call records where each row contains a caller, a recipient, and a timestamp. Each call is bidirectional in the sense that both participants are considered to have made and received the call simultaneously.

leetcodeharddatabase

LeetCode Problem 1972

Difficulty: 🔴 Hard
Topics: Database

Solution

Problem Understanding

The problem provides a table of phone call records where each row contains a caller, a recipient, and a timestamp. Each call is bidirectional in the sense that both participants are considered to have made and received the call simultaneously. The goal is to identify all users who, on at least one calendar day, had their first call and their last call involving the same counterpart user.

Rephrased more precisely, for every user and for every day on which they participated in at least one call, we must consider the sequence of calls involving that user on that day (regardless of whether they were caller or recipient). If the earliest call of that day and the latest call of that day both involve the same other user, then that user qualifies for the result.

The input is a relational dataset of call events. The output is a set of user IDs, deduplicated, representing users who satisfy the condition for at least one day.

Although the problem is framed as a database task, it fundamentally requires grouping events by user and day, ordering them by time, and checking boundary conditions.

The constraints imply potentially large input size, so an O(n log n) or O(n) grouping solution is expected depending on indexing strategy. A naive comparison of every call against every other call would be too slow.

Important edge cases include users with only one call in a day, multiple calls with different partners, calls spanning multiple days, and ensuring symmetry between caller and recipient. Another subtle case is that a user may qualify on one day even if they do not qualify on others, and we only need at least one qualifying day.

Approaches

The brute-force approach simulates the problem literally. For each user and each day, we would collect all calls involving that user, sort them by time, and compare the first and last call partners. However, doing this independently for each user-day pair by repeatedly scanning the full dataset leads to redundant work and high computational cost.

The optimal approach recognizes that each call contributes to two users, and we can preprocess all events into a structure grouped by (user_id, date). Within each group, we only need to track chronological ordering of calls and compare endpoints. This avoids repeated full scans and reduces the problem to efficient grouping and sorting.

Approach Time Complexity Space Complexity Notes
Brute Force O(U × D × N log N) O(N) For each user-day, rescan and sort calls
Optimal Grouping O(N log N) O(N) Group per user-day, sort within groups

Algorithm Walkthrough

The optimal solution is built on the idea of transforming each call into two directional events so that every user can independently analyze their own call timeline.

  1. First, we iterate through every call record. For each call between a caller and recipient at a given timestamp, we create two events: one for the caller and one for the recipient. This normalization ensures that every user has a complete view of their own call history without needing to reason about directionality.
  2. We extract the date portion from the timestamp because the condition is evaluated per calendar day. This allows us to group calls into independent daily buckets per user.
  3. We store these events in a dictionary keyed by (user_id, date). Each value is a list of (time, other_user) pairs, representing when the user interacted and with whom.
  4. After building the structure, we iterate over each (user_id, date) group. We sort the events by time to reconstruct the chronological sequence of calls for that user on that day.
  5. Once sorted, we inspect the first and last entries in the list. If the “other_user” in both positions is identical, it means the first and last calls of that day involved the same person, so we include the user in the result set.
  6. Finally, we return all qualifying user IDs, deduplicated.

Why it works

The key invariant is that sorting the per-user-per-day event list reconstructs the exact chronological order of participation for that user. Since we explicitly check only the first and last interactions, we are directly validating the problem condition without needing to examine intermediate calls.

Python Solution

from typing import List, Tuple, Dict
from collections import defaultdict
from datetime import datetime

class Solution:
    def firstLastCall(self, calls: List[Tuple[int, int, str]]) -> List[int]:
        user_day_map: Dict[Tuple[int, str], List[Tuple[str, int]]] = defaultdict(list)

        for caller, recipient, call_time in calls:
            date = call_time.split(" ")[0]

            user_day_map[(caller, date)].append((call_time, recipient))
            user_day_map[(recipient, date)].append((call_time, caller))

        result = set()

        for (user_id, date), events in user_day_map.items():
            events.sort(key=lambda x: x[0])

            if events[0][1] == events[-1][1]:
                result.add(user_id)

        return list(result)

Code Explanation

The solution starts by building a dictionary that groups call events by user and date. Each call contributes two entries so that both participants maintain their own timeline.

The date is extracted from the timestamp string, which is sufficient because the ordering within a day is still preserved lexicographically by the full timestamp.

After grouping, each list of events is sorted by timestamp to ensure chronological correctness. We then compare the first and last “other participant” values. If they match, that user satisfies the condition for that day.

We use a set to avoid duplicates since a user may satisfy the condition on multiple days.

Go Solution

package main

import (
    "sort"
    "strings"
)

type Event struct {
    time   string
    other  int
}

func firstLastCall(calls [][]string) []int {
    type key struct {
        user int
        date string
    }

    groups := make(map[key][]Event)

    for _, c := range calls {
        caller := atoi(c[0])
        recipient := atoi(c[1])
        time := c[2]

        date := strings.Split(time, " ")[0]

        groups[key{caller, date}] = append(groups[key{caller, date}], Event{time, recipient})
        groups[key{recipient, date}] = append(groups[key{recipient, date}], Event{time, caller})
    }

    resSet := make(map[int]bool)

    for k, events := range groups {
        sort.Slice(events, func(i, j int) bool {
            return events[i].time < events[j].time
        })

        if len(events) > 0 && events[0].other == events[len(events)-1].other {
            resSet[k.user] = true
        }
    }

    res := make([]int, 0, len(resSet))
    for id := range resSet {
        res = append(res, id)
    }

    return res
}

func atoi(s string) int {
    n := 0
    for i := 0; i < len(s); i++ {
        n = n*10 + int(s[i]-'0')
    }
    return n
}

Go-specific Notes

Go requires explicit type definitions for grouping keys, so a struct is used for (user, date). Sorting is done with sort.Slice, and string splitting is used to extract dates. Since Go lacks built-in string-to-int conversion in this simplified snippet, a manual atoi function is included. Maps are used for both grouping and deduplication.

Worked Examples

Consider the input where user 8 has multiple calls on the same day. We first expand calls:

Call (8 → 4 at 17:46) becomes:

user 8: (17:46, 4)

user 4: (17:46, 8)

Call (4 → 8 at 19:57) becomes:

user 8: (19:57, 4)

user 4: (19:57, 8)

For user 8 on 2021-08-24, after sorting:

(17:46, 4), (19:57, 4)

First partner = 4, last partner = 4, so user 8 qualifies.

For user 4 on the same day:

(17:46, 8), (19:57, 8)

First partner = 8, last partner = 8, so user 4 qualifies.

For a single-call day like user 1 and 5:

Only one event exists per user, so first and last are identical by definition, and both qualify.

Complexity Analysis

Measure Complexity Explanation
Time O(N log N) Each call is processed twice, and sorting is applied per user-day group
Space O(N) Storage of expanded events for both participants

The dominant factor is sorting within grouped call lists. While grouping itself is linear, sorting introduces logarithmic overhead per group, yielding overall O(N log N) behavior in the worst case.

Test Cases

# basic example
assert set(Solution().firstLastCall([
    (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")
])) == {1, 4, 5, 8}  # original example

# single call only
assert set(Solution().firstLastCall([
    (1, 2, "2021-01-01 10:00:00")
])) == {1, 2}  # both qualify

# multiple calls different partners
assert set(Solution().firstLastCall([
    (1, 2, "2021-01-01 10:00:00"),
    (1, 3, "2021-01-01 11:00:00"),
    (1, 4, "2021-01-01 12:00:00")
])) == set()  # no match

# same partner but not first/last
assert set(Solution().firstLastCall([
    (1, 2, "2021-01-01 10:00:00"),
    (1, 3, "2021-01-01 11:00:00"),
    (1, 2, "2021-01-01 12:00:00")
])) == set()  # first and last differ
Test Why
example input validates full problem statement behavior
single call checks trivial first equals last case
multiple partners ensures rejection when endpoints differ
non-matching endpoints verifies ordering sensitivity

Edge Cases

One important edge case is when a user has exactly one call in a day. In this case, that call is simultaneously the first and last call, so the user should always qualify. The implementation handles this naturally because the event list contains a single element, and both endpoints are identical.

Another edge case involves multiple calls with the same partner but interleaved with others. The ordering matters strictly by time, so even if a user repeatedly calls the same person, the first and last call must still match that same partner; otherwise, they are disqualified. Sorting ensures we correctly capture this ordering.

A third edge case is ensuring bidirectional inclusion. A call must be recorded for both participants, otherwise one side of the interaction would be missing and the result would be incorrect. By explicitly inserting mirrored events for caller and recipient, we guarantee symmetry.

A final edge case involves multiple qualifying days per user. The solution correctly uses a set, ensuring each user is included only once regardless of how many days they satisfy the condition.