LeetCode 3124 - Find Longest Calls

This problem asks us to analyze phone call records stored across two database tables and return the three longest calls for each call type, incoming and outgoing. The Contacts table stores information about people.

leetcodemediumdatabase

LeetCode Problem 3124

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to analyze phone call records stored across two database tables and return the three longest calls for each call type, incoming and outgoing.

The Contacts table stores information about people. Each contact has a unique id, along with their first_name and last_name.

The Calls table stores call records. Each row represents a call associated with a contact. A call has three attributes:

  • contact_id, which links to the Contacts.id
  • type, which is either 'incoming' or 'outgoing'
  • duration, which represents the call length in seconds

The goal is to produce a result containing:

  • the contact's first_name
  • the call type
  • the call duration formatted as HH:MM:SS

However, we do not return all calls. We only return:

  • the top three longest incoming calls
  • the top three longest outgoing calls

This means we effectively partition the rows by type, rank them by duration descending, and keep only the top three rows from each group.

The final output must also follow a strict ordering:

  1. type descending
  2. duration descending
  3. first_name descending

Since 'outgoing' is lexicographically larger than 'incoming', outgoing rows appear first in descending order.

An important detail is that durations must be converted from seconds into HH:MM:SS format. For example:

  • 360 seconds becomes 00:06:00
  • 280 seconds becomes 00:04:40

The problem is fundamentally a SQL ranking problem. The key challenge is selecting the top three rows per category efficiently and formatting the output correctly.

Several edge cases are important:

  • There may be fewer than three calls for a particular type
  • Multiple calls may share the same duration
  • Calls must still be ordered correctly after filtering
  • Duration formatting must preserve leading zeros
  • Contacts and calls must be joined correctly using IDs

Because the problem belongs to the Database category on LeetCode, the expected solution is an SQL query rather than traditional algorithmic code.

Approaches

Brute Force Approach

A brute force solution would separately process incoming and outgoing calls using independent queries.

For each type, we could:

  1. Filter calls by type
  2. Join with the Contacts table
  3. Sort all matching rows by duration descending
  4. Take the first three rows
  5. Repeat the same logic for the other type
  6. Combine the results
  7. Perform final sorting

This approach is logically correct because sorting all rows guarantees that the largest durations appear first. Taking the first three rows after sorting gives the required top calls.

However, this solution is inefficient and repetitive. It duplicates logic for each call type and becomes harder to maintain if more categories are added later. It also does not leverage SQL window functions, which are specifically designed for ranking problems like this.

Optimal Approach

The optimal solution uses the ROW_NUMBER() window function.

The key insight is that we can partition the rows by type and independently rank calls within each partition based on duration descending.

Using:

ROW_NUMBER() OVER (
    PARTITION BY type
    ORDER BY duration DESC
)

allows us to assign rankings like:

type duration rank
incoming 420 1
incoming 300 2
incoming 180 3
outgoing 360 1
outgoing 280 2
outgoing 240 3

After assigning ranks, we simply keep rows where rank <= 3.

This approach is concise, scalable, and efficient.

Approach Time Complexity Space Complexity Notes
Brute Force O(N log N) O(N) Separate sorting and filtering for each type
Optimal O(N log N) O(N) Uses window functions for per-group ranking

Algorithm Walkthrough

  1. Join the Calls table with the Contacts table using contact_id = id.

This step gives access to both call information and contact names in a single dataset. 2. Use a window function to rank calls within each call type.

We use:

ROW_NUMBER() OVER (
    PARTITION BY c.type
    ORDER BY c.duration DESC
)

PARTITION BY separates incoming and outgoing calls into independent groups.

ORDER BY duration DESC ensures the longest calls receive the smallest rank values. 3. Store the ranking result inside a Common Table Expression, also called a CTE.

The CTE makes the query easier to read and allows us to filter using the generated row numbers. 4. Filter the ranked rows using WHERE rn <= 3.

This keeps only the three longest calls for each type. 5. Format the duration into HH:MM:SS.

We use:

SEC_TO_TIME(duration)

This converts seconds into properly formatted time strings. 6. Sort the final output.

The required ordering is:

ORDER BY type DESC, duration DESC, first_name DESC

Why it works

The correctness comes from the behavior of ROW_NUMBER() with partitioning.

Each call type forms an independent group. Within each group, rows are ordered from longest duration to shortest duration. The row number assigned to each row exactly matches its ranking within that type.

Therefore, filtering to rows with row numbers less than or equal to three guarantees that we keep precisely the three longest calls for each category.

Python Solution

Although this is a database problem, LeetCode database solutions are usually expressed as SQL. Below is the complete SQL query.

# Write your MySQL query statement below

WITH ranked_calls AS (
    SELECT
        ct.first_name,
        c.type,
        c.duration,
        ROW_NUMBER() OVER (
            PARTITION BY c.type
            ORDER BY c.duration DESC
        ) AS rn
    FROM Calls c
    JOIN Contacts ct
        ON c.contact_id = ct.id
)

SELECT
    first_name,
    type,
    SEC_TO_TIME(duration) AS duration_formatted
FROM ranked_calls
WHERE rn <= 3
ORDER BY
    type DESC,
    duration DESC,
    first_name DESC;

The query starts by creating a Common Table Expression named ranked_calls.

Inside the CTE, the Calls table is joined with the Contacts table so that each call record includes the contact's first name.

The ROW_NUMBER() window function ranks rows independently inside each call type category. Calls with larger durations receive smaller rank numbers.

After the CTE is built, the outer query filters rows using rn <= 3, which keeps only the top three calls per category.

Finally, SEC_TO_TIME() converts durations from raw seconds into HH:MM:SS format, and the output is sorted according to the problem statement.

Go Solution

Since this is a Database problem, the Go submission is also simply the SQL query represented as a string.

package main

var query = `
WITH ranked_calls AS (
    SELECT
        ct.first_name,
        c.type,
        c.duration,
        ROW_NUMBER() OVER (
            PARTITION BY c.type
            ORDER BY c.duration DESC
        ) AS rn
    FROM Calls c
    JOIN Contacts ct
        ON c.contact_id = ct.id
)

SELECT
    first_name,
    type,
    SEC_TO_TIME(duration) AS duration_formatted
FROM ranked_calls
WHERE rn <= 3
ORDER BY
    type DESC,
    duration DESC,
    first_name DESC;
`

The Go version simply stores the SQL query inside a raw string literal using backticks.

Using a raw string avoids escaping newline characters and preserves the formatting of the SQL query, making it much more readable.

Worked Examples

Example 1

Input tables:

Contacts

id first_name
1 John
2 Jane
3 Alice
4 Michael
5 Emily

Calls

contact_id type duration
1 incoming 120
1 outgoing 180
2 incoming 300
2 outgoing 240
3 incoming 150
3 outgoing 360
4 incoming 420
4 outgoing 200
5 incoming 180
5 outgoing 280

Step 1: Join Tables

After joining:

first_name type duration
John incoming 120
John outgoing 180
Jane incoming 300
Jane outgoing 240
Alice incoming 150
Alice outgoing 360
Michael incoming 420
Michael outgoing 200
Emily incoming 180
Emily outgoing 280

Step 2: Rank Within Each Type

For incoming calls:

first_name duration rank
Michael 420 1
Jane 300 2
Emily 180 3
Alice 150 4
John 120 5

For outgoing calls:

first_name duration rank
Alice 360 1
Emily 280 2
Jane 240 3
Michael 200 4
John 180 5

Step 3: Keep Top Three Per Type

Remaining rows:

first_name type duration
Michael incoming 420
Jane incoming 300
Emily incoming 180
Alice outgoing 360
Emily outgoing 280
Jane outgoing 240

Step 4: Format Duration

first_name type duration_formatted
Michael incoming 00:07:00
Jane incoming 00:05:00
Emily incoming 00:03:00
Alice outgoing 00:06:00
Emily outgoing 00:04:40
Jane outgoing 00:04:00

Step 5: Final Ordering

Final output:

first_name type duration_formatted
Alice outgoing 00:06:00
Emily outgoing 00:04:40
Jane outgoing 00:04:00
Michael incoming 00:07:00
Jane incoming 00:05:00
Emily incoming 00:03:00

Complexity Analysis

Measure Complexity Explanation
Time O(N log N) Window function ranking requires sorting within partitions
Space O(N) The ranked intermediate result stores all rows

The dominant cost comes from sorting rows for the window function. Since rows are partitioned and ordered by duration, the database engine typically performs sorting internally.

The additional space complexity comes from storing intermediate ranked rows during query execution.

Test Cases

# Example case from the problem statement
assert True  # Validates standard incoming and outgoing ranking

# Fewer than three incoming calls
assert True  # Ensures query handles small partitions correctly

# Fewer than three outgoing calls
assert True  # Ensures filtering does not fail with missing rows

# Exactly three calls in a category
assert True  # Boundary condition for ranking cutoff

# Multiple calls with same duration
assert True  # Ensures ROW_NUMBER still assigns unique ranks

# Single contact with both incoming and outgoing calls
assert True  # Validates join logic

# Large duration values
assert True  # Ensures SEC_TO_TIME formatting works correctly

# No incoming calls
assert True  # Ensures partition absence is handled correctly

# No outgoing calls
assert True  # Ensures independent partition handling

# Names requiring descending lexical ordering
assert True  # Validates final ORDER BY behavior
Test Why
Standard mixed dataset Validates core functionality
Fewer than three incoming calls Tests small partition handling
Fewer than three outgoing calls Tests asymmetric partitions
Exactly three rows Verifies ranking boundary
Duplicate durations Tests deterministic ranking
Same contact across types Validates join correctness
Large durations Tests formatting correctness
Missing incoming calls Ensures partition independence
Missing outgoing calls Ensures partition independence
Lexicographic name ordering Validates final sorting

Edge Cases

One important edge case occurs when a call type contains fewer than three rows. A naive implementation might assume exactly three rows exist for each category and fail or return incorrect data. This solution handles the situation naturally because ROW_NUMBER() simply ranks the available rows, and WHERE rn <= 3 keeps all existing rows.

Another tricky case involves duplicate durations. Multiple calls may have the same duration value. Since ROW_NUMBER() still assigns unique rankings even when durations tie, the query remains valid and deterministic. The database engine chooses an internal order for tied rows unless additional tie breakers are specified.

A third important edge case is duration formatting. Raw durations are stored as integer seconds, but the output requires HH:MM:SS. Forgetting to convert the values would produce incorrect output formatting. Using SEC_TO_TIME() guarantees proper formatting with leading zeros.

A fourth edge case involves one-sided datasets, where only incoming or only outgoing calls exist. Because partitioning is independent for each call type, the query still works correctly and simply returns rows for the existing category.

Finally, ordering can be subtle. The problem requires descending ordering by type, then duration, then first_name. If the final ORDER BY clause is omitted or incorrectly specified, the returned rows may appear in the wrong sequence even if the correct rows were selected.