LeetCode 2984 - Find Peak Calling Hours for Each City

LeetCode Problem 2984

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

The problem is asking us to analyze call records from a Calls table and determine the peak calling hour for each city. Each row in the table contains a caller_id, recipient_id, a timestamp (call_time), and the city where the call originated. The goal is to find which hour(s) of the day (0-23) saw the maximum number of calls for each city. If multiple hours have the same maximum number of calls, all of them are considered peak hours. The final result should be ordered first by the peak calling hour in descending order, then by city in descending order.

The input represents a real-world call log, with each call potentially happening at any datetime. The output aggregates calls by city and hour of day, and counts the calls to determine peaks.

Key points to note are that call_time is a datetime field, so extracting the hour is necessary. The problem guarantees that (caller_id, recipient_id, call_time) is unique, so we will not have duplicate call entries.

Important edge cases include cities with only one call, multiple hours sharing the same maximum count, and calls that occur exactly at the boundary of hours (e.g., 13:00:00 vs 13:59:59).

Approaches

A brute-force approach would involve iterating over each city, iterating over every hour (0-23), counting the number of calls in that hour, and then comparing the counts to find the maximum. While this works, it is inefficient because it involves repeatedly scanning the entire table for each city-hour combination. For large datasets, this leads to excessive computations.

The optimal approach leverages SQL aggregation and window functions. The key insight is that we can group by city and hour to compute call counts in one pass, and then use a window function to find the maximum call count per city. Filtering for rows that match the maximum count per city yields all peak hours, including ties. This approach is efficient because it only scans the table once and lets the database engine handle the heavy lifting.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * 24 * c)	O(n)	For each city and hour, count calls manually. Inefficient for large n.
Optimal	O(n)	O(n)	Aggregate calls per city-hour and use window function to find peaks. Scales well with table size.

Algorithm Walkthrough

1. Extract the hour from the call_time column. This will allow us to group calls by hour.
2. Use a GROUP BY clause to aggregate the number of calls for each combination of city and hour.
3. For each city, find the maximum call count. This can be achieved using a window function with MAX() partitioned by city.
4. Filter rows where the number_of_calls equals the maximum call count for that city. This step ensures that if multiple hours have the same peak number, they all are included.
5. Order the results by peak_calling_hour descending, then by city descending, as required by the problem.

Why it works: The algorithm ensures that all calls are counted per city-hour, and the window function guarantees we correctly identify all peak hours, including ties. The ordering in the final step respects the problem's constraints for the output format.

Python Solution

# Since this is a SQL problem, Python solution involves executing the query
def findPeakCallingHours(connection) -> list[tuple]:
    query = """
    WITH call_counts AS (
        SELECT
            city,
            EXTRACT(HOUR FROM call_time) AS peak_calling_hour,
            COUNT(*) AS number_of_calls
        FROM Calls
        GROUP BY city, EXTRACT(HOUR FROM call_time)
    ),
    max_counts AS (
        SELECT
            city,
            MAX(number_of_calls) AS max_calls
        FROM call_counts
        GROUP BY city
    )
    SELECT
        c.city,
        c.peak_calling_hour,
        c.number_of_calls
    FROM call_counts c
    JOIN max_counts m
      ON c.city = m.city AND c.number_of_calls = m.max_calls
    ORDER BY c.peak_calling_hour DESC, c.city DESC
    """
    with connection.cursor() as cursor:
        cursor.execute(query)
        result = cursor.fetchall()
    return result

The Python implementation executes a SQL query that performs the grouping, aggregation, and filtering directly in the database. The first CTE (call_counts) computes the number of calls per city-hour. The second CTE (max_counts) computes the maximum number of calls per city. We then join them to select only the rows where the call count equals the maximum.

Go Solution

package main

import (
    "database/sql"
)

func FindPeakCallingHours(db *sql.DB) ([][3]interface{}, error) {
    query := `
    WITH call_counts AS (
        SELECT
            city,
            EXTRACT(HOUR FROM call_time) AS peak_calling_hour,
            COUNT(*) AS number_of_calls
        FROM Calls
        GROUP BY city, EXTRACT(HOUR FROM call_time)
    ),
    max_counts AS (
        SELECT
            city,
            MAX(number_of_calls) AS max_calls
        FROM call_counts
        GROUP BY city
    )
    SELECT
        c.city,
        c.peak_calling_hour,
        c.number_of_calls
    FROM call_counts c
    JOIN max_counts m
      ON c.city = m.city AND c.number_of_calls = m.max_calls
    ORDER BY c.peak_calling_hour DESC, c.city DESC;
    `
    rows, err := db.Query(query)
    if err != nil {
        return nil, err
    }
    defer rows.Close()

    var results [][3]interface{}
    for rows.Next() {
        var city string
        var hour int
        var count int
        if err := rows.Scan(&city, &hour, &count); err != nil {
            return nil, err
        }
        results = append(results, [3]interface{}{city, hour, count})
    }
    return results, nil
}

The Go implementation is similar to the Python approach but uses the database/sql package. Each row is scanned and stored in a slice of fixed-size arrays. Go handles types strictly, so integers and strings must match the query's output columns.

Worked Examples

Using the problem's example:

Input table Calls:

caller_id	recipient_id	call_time	city
8	4	2021-08-24 22:46:07	Houston
4	8	2021-08-24 22:57:13	Houston
5	1	2021-08-11 21:28:44	Houston
8	3	2021-08-17 22:04:15	Houston
11	3	2021-08-17 13:07:00	New York
8	11	2021-08-17 14:22:22	New York

Step-by-step:

1. Extract hour from call_time → Houston: 22, 22, 21, 22; New York: 13, 14
2. Count per city-hour → Houston: 21→1, 22→3; New York: 13→1, 14→1
3. Compute max per city → Houston: 3, New York: 1
4. Filter → Houston: 22 (3), New York: 13 (1), 14 (1)
5. Order → peak_calling_hour descending, city descending → Houston 22, New York 14, New York 13

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	The query scans the Calls table once to group by city-hour, and joins a small aggregated table.
Space	O(n)	Storing aggregated counts per city-hour; database may optimize further with internal structures.

The optimal solution is linear relative to the number of rows in the table, assuming the number of distinct hours per city is bounded (0-23).

Test Cases

# Provided example
assert findPeakCallingHours(connection) == [
    ('Houston', 22, 3),
    ('New York', 14, 1),
    ('New York', 13, 1)
]

# Single city, single call
assert findPeakCallingHours(connection) == [
    ('Chicago', 10, 1)
]

# Multiple cities, multiple peak hours tie
assert findPeakCallingHours(connection) == [
    ('Boston', 16, 2),
    ('Boston', 17, 2),
    ('Denver', 9, 1),
    ('Denver', 12, 1)
]

# All calls at same hour
assert findPeakCallingHours(connection) == [
    ('Seattle', 15, 5)
]

Test	Why
Provided example	Validates basic functionality and ordering
Single city, single call	Edge case with minimal data
Multiple peak hours tie	Tests handling of tie hours per city
All calls at same hour	Confirms correct counting when all calls fall into same hour

Edge Cases

First