LeetCode 3705 - Find Golden Hour Customers

This problem asks us to identify "golden hour customers" from a restaurant's order history. A golden hour customer is defined as someone who consistently orders during peak hours and maintains high satisfaction.

leetcodemedium

LeetCode Problem 3705

Difficulty: 🟡 Medium
Topics: —

Solution

Problem Understanding

This problem asks us to identify "golden hour customers" from a restaurant's order history. A golden hour customer is defined as someone who consistently orders during peak hours and maintains high satisfaction. Specifically, a customer must meet all of the following conditions: they must have made at least three orders, at least 60% of their orders must fall within peak hours (11:00-14:00 for lunch or 18:00-21:00 for dinner), at least 50% of their orders must be rated, and the average rating of their rated orders must be at least 4.0 when rounded to two decimal places.

The input is a restaurant_orders table with each row representing a single order, including the order ID, customer ID, timestamp, amount, payment method, and an optional rating. The output is a table of customers who satisfy all golden hour criteria, including the total number of orders, the percentage of peak hour orders, and the average rating. The output must be ordered by average_rating descending and then customer_id descending.

Key considerations include handling NULL ratings, computing percentages correctly (especially fractional values like 2 out of 3), and correctly identifying peak hours. Edge cases include customers with exactly three orders, exactly 50% of orders rated, or exactly 60% of orders in peak hours.

Approaches

The brute-force approach involves iterating through all orders for each customer and computing the relevant counts and averages manually. While conceptually simple, this approach can become slow if the table contains millions of rows because it repeatedly scans all orders per customer.

The optimal approach leverages SQL aggregate functions. By grouping orders by customer_id, we can efficiently compute the total number of orders, peak hour counts, rated order counts, and sum of ratings in a single pass. Conditional aggregation allows us to compute peak hour orders and rated orders in the same query. Using these aggregates, we can filter customers meeting all golden hour criteria and compute derived metrics like peak hour percentage and average rating. Finally, we order the results as specified.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(n) Iterates through all orders per customer repeatedly, inefficient for large tables
Optimal O(n) O(c) Single aggregation per customer using SQL GROUP BY, scalable and efficient

Algorithm Walkthrough

  1. Group all orders by customer_id to compute per-customer aggregates. Count total orders, count rated orders (non-NULL order_rating), sum the ratings, and count peak hour orders.
  2. For peak hour orders, check if order_timestamp hour falls within 11-14 or 18-21. Use conditional aggregation (CASE WHEN ... THEN 1 ELSE 0 END) for counting.
  3. Calculate derived metrics: peak_hour_percentage = (peak_hour_orders / total_orders) * 100 and average_rating = sum_rating / rated_orders.
  4. Filter customers based on the four golden hour criteria: total orders >= 3, peak hour percentage >= 60, rated orders >= 50% of total, and average rating >= 4.0.
  5. Round the average_rating to two decimal places.
  6. Order the results first by average_rating descending, then by customer_id descending.

This algorithm works because all relevant metrics are computed per customer in a single aggregation, ensuring correct counts and averages without repeatedly scanning the data.

Python Solution

import sqlite3

def find_golden_hour_customers(conn: sqlite3.Connection):
    query = """
    WITH customer_stats AS (
        SELECT
            customer_id,
            COUNT(*) AS total_orders,
            SUM(CASE WHEN order_rating IS NOT NULL THEN 1 ELSE 0 END) AS rated_orders,
            SUM(CASE WHEN (CAST(strftime('%H', order_timestamp) AS INTEGER) BETWEEN 11 AND 14)
                     OR (CAST(strftime('%H', order_timestamp) AS INTEGER) BETWEEN 18 AND 21)
                     THEN 1 ELSE 0 END) AS peak_hour_orders,
            SUM(CASE WHEN order_rating IS NOT NULL THEN order_rating ELSE 0 END) AS sum_rating
        FROM restaurant_orders
        GROUP BY customer_id
    )
    SELECT
        customer_id,
        total_orders,
        ROUND(peak_hour_orders * 100.0 / total_orders, 0) AS peak_hour_percentage,
        ROUND(sum_rating * 1.0 / rated_orders, 2) AS average_rating
    FROM customer_stats
    WHERE total_orders >= 3
      AND peak_hour_orders * 1.0 / total_orders >= 0.6
      AND rated_orders * 1.0 / total_orders >= 0.5
      AND sum_rating * 1.0 / rated_orders >= 4.0
    ORDER BY average_rating DESC, customer_id DESC;
    """
    cursor = conn.cursor()
    cursor.execute(query)
    return cursor.fetchall()

This Python solution uses SQLite for SQL execution. We first compute per-customer aggregates using a common table expression, then filter and compute derived metrics. The strftime function extracts the hour, and conditional aggregation counts peak hour orders and rated orders. The final selection filters golden hour customers and orders them as required.

Go Solution

package main

import (
    "database/sql"
    _ "github.com/mattn/go-sqlite3"
    "fmt"
)

func FindGoldenHourCustomers(db *sql.DB) ([]map[string]interface{}, error) {
    query := `
    WITH customer_stats AS (
        SELECT
            customer_id,
            COUNT(*) AS total_orders,
            SUM(CASE WHEN order_rating IS NOT NULL THEN 1 ELSE 0 END) AS rated_orders,
            SUM(CASE WHEN (CAST(strftime('%H', order_timestamp) AS INTEGER) BETWEEN 11 AND 14)
                     OR (CAST(strftime('%H', order_timestamp) AS INTEGER) BETWEEN 18 AND 21)
                     THEN 1 ELSE 0 END) AS peak_hour_orders,
            SUM(CASE WHEN order_rating IS NOT NULL THEN order_rating ELSE 0 END) AS sum_rating
        FROM restaurant_orders
        GROUP BY customer_id
    )
    SELECT
        customer_id,
        total_orders,
        ROUND(peak_hour_orders * 100.0 / total_orders, 0) AS peak_hour_percentage,
        ROUND(sum_rating * 1.0 / rated_orders, 2) AS average_rating
    FROM customer_stats
    WHERE total_orders >= 3
      AND peak_hour_orders * 1.0 / total_orders >= 0.6
      AND rated_orders * 1.0 / total_orders >= 0.5
      AND sum_rating * 1.0 / rated_orders >= 4.0
    ORDER BY average_rating DESC, customer_id DESC;
    `
    rows, err := db.Query(query)
    if err != nil {
        return nil, err
    }
    defer rows.Close()

    var results []map[string]interface{}
    for rows.Next() {
        var customerID int
        var totalOrders int
        var peakHourPercentage float64
        var averageRating float64
        err = rows.Scan(&customerID, &totalOrders, &peakHourPercentage, &averageRating)
        if err != nil {
            return nil, err
        }
        results = append(results, map[string]interface{}{
            "customer_id":          customerID,
            "total_orders":         totalOrders,
            "peak_hour_percentage": peakHourPercentage,
            "average_rating":       averageRating,
        })
    }
    return results, nil
}

The Go solution mirrors the Python approach. Differences include using sql.DB and Query to execute the SQL, scanning into typed variables, and appending to a slice of maps for return. We handle NULL ratings automatically using SQL aggregation.

Worked Examples

For customer 101: total orders = 4, peak hour orders = 4, rated orders = 3, sum_rating = 14. Derived metrics: peak_hour_percentage = 100%, average_rating = 14/3 = 4.67. All thresholds met, so included.

For customer 102: total orders = 3, peak hour orders = 2, rated orders = 2, sum_rating = 7. Derived metrics: peak_hour_percentage ≈ 66.67%, average_rating = 3.5. Average rating < 4.0, excluded.

For customer 103: total orders = 3, peak hour orders = 3, rated orders = 3, sum_rating = 14. Derived metrics: peak_hour_percentage = 100%, average_rating = 4.67. Included.

For customer 105: total orders = 3, peak hour orders = 3, rated orders = 3, sum_rating = 13. Derived metrics: peak_hour_percentage = 100%, average_rating = 4.33. Included.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single scan of all orders to compute aggregates
Space O(c) One row per customer in memory during aggregation

The approach scales linearly with the number of orders, and memory scales with the number of unique customers rather than total orders.

Test Cases

# Provided example
assert find_golden_hour_customers(conn) == [
    (103, 3, 100, 4.67),
    (101, 4, 100, 4.67),
    (105, 3, 100, 4.33)
]

# Edge: customer with exactly 3 orders, 2 rated, meets thresholds
# Edge: customer with peak orders