LeetCode 3118 - Friday Purchase III

LeetCode Problem 3118

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to calculate the total amount of money spent by Premium and VIP members on Fridays of each week in November 2023. The inputs are two tables: Purchases, which records the user_id, purchase_date, and amount_spend, and Users, which records the user_id and their membership type.

We need to aggregate spending only for Premium and VIP members for each Friday, grouped by the week of the month. If no purchases occurred for a given membership on a Friday, the total should be reported as 0. Finally, the output must be ordered by the week of the month ascending and membership ascending.

The constraints tell us that dates are limited to November 2023 and the Purchases table has a primary key on (user_id, purchase_date, amount_spend), which guarantees no duplicate entries. Edge cases include Fridays with no purchases, weeks with only one type of membership buying something, and weeks with multiple purchases from multiple members.

Key points are to calculate the week of the month correctly and to ensure that missing combinations of week and membership are represented as 0.

Approaches

The brute-force approach would involve first generating a list of all Fridays in November 2023, joining with the Users table to filter only Premium and VIP members, then summing amount_spend for each Friday. For missing entries, we would need a post-processing step to fill zeros. This approach is correct but cumbersome and verbose, as generating all combinations and filling zeros manually in SQL requires multiple subqueries or union operations.

The optimal approach leverages SQL's calendar table generation and aggregations with GROUP BY, combined with a LEFT JOIN to handle Fridays with no purchases. By generating all Fridays and cross-joining with the membership types Premium and VIP, we can then LEFT JOIN with actual purchases to sum spending and default missing values to 0 using COALESCE. This approach is concise, efficient, and directly produces the required output structure.

Algorithm Walkthrough

1. Generate a list of all Fridays in November 2023. This can be done using GENERATE_SERIES in SQL or equivalent, starting at 2023-11-01, ending at 2023-11-30, incrementing by 1 day, then filtering for Fridays.
2. Determine the week of the month for each Friday using a formula like (DAY(purchase_date) + 6) / 7 and take the floor or integer division.
3. Define the set of relevant membership types, which are Premium and VIP.
4. Form the cross join between all Fridays and relevant memberships to get every possible (week_of_month, membership) combination.
5. Aggregate the Purchases table by week_of_month and membership after joining with Users to filter only Premium and VIP purchases.
6. Perform a LEFT JOIN between the cross join of all Fridays and memberships with the aggregated purchases.
7. Use COALESCE to convert NULLs in total spend to 0.
8. Order the final result by week_of_month ascending and membership ascending.

Why it works: The cross join ensures all combinations of Fridays and memberships exist. The LEFT JOIN guarantees that missing purchase data becomes NULL, which we convert to 0. Aggregation ensures multiple purchases are summed per Friday and membership.

Python Solution

import sqlite3

def friday_purchase_iii():
    query = """
    WITH Fridays AS (
        SELECT date('2023-11-01', '+' || (n) || ' day') AS purchase_date
        FROM (SELECT 0 AS n UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4
              UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9
              UNION ALL SELECT 10 UNION ALL SELECT 11 UNION ALL SELECT 12 UNION ALL SELECT 13 UNION ALL SELECT 14
              UNION ALL SELECT 15 UNION ALL SELECT 16 UNION ALL SELECT 17 UNION ALL SELECT 18 UNION ALL SELECT 19
              UNION ALL SELECT 20 UNION ALL SELECT 21 UNION ALL SELECT 22 UNION ALL SELECT 23 UNION ALL SELECT 24
              UNION ALL SELECT 25 UNION ALL SELECT 26 UNION ALL SELECT 27 UNION ALL SELECT 28 UNION ALL SELECT 29) AS days
        WHERE strftime('%w', date('2023-11-01', '+' || n || ' day')) = '5'
    ),
    PurchasesAgg AS (
        SELECT
            ((CAST(strftime('%d', p.purchase_date) AS INTEGER) + 6) / 7) AS week_of_month,
            u.membership,
            SUM(p.amount_spend) AS total_amount
        FROM Purchases p
        JOIN Users u ON p.user_id = u.user_id
        WHERE u.membership IN ('Premium', 'VIP')
        GROUP BY week_of_month, membership
    ),
    FridaysMembership AS (
        SELECT
            ((CAST(strftime('%d', f.purchase_date) AS INTEGER) + 6) / 7) AS week_of_month,
            m.membership
        FROM Fridays f
        CROSS JOIN (SELECT 'Premium' AS membership UNION ALL SELECT 'VIP') m
    )
    SELECT 
        fm.week_of_month,
        fm.membership,
        COALESCE(pa.total_amount, 0) AS total_amount
    FROM FridaysMembership fm
    LEFT JOIN PurchasesAgg pa
    ON fm.week_of_month = pa.week_of_month AND fm.membership = pa.membership
    ORDER BY fm.week_of_month, fm.membership;
    """
    return query

Explanation: First, Fridays generates all Fridays in November. PurchasesAgg sums amounts by week and membership. FridaysMembership creates all combinations of week_of_month and membership types. The final SELECT LEFT JOINs the aggregated data with all combinations and fills missing totals with 0 using COALESCE.

Go Solution

package main

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

func fridayPurchaseIII(db *sql.DB) (*sql.Rows, error) {
    query := `
    WITH Fridays AS (
        SELECT date('2023-11-01', '+' || (n) || ' day') AS purchase_date
        FROM (SELECT 0 AS n UNION ALL SELECT 1 UNION ALL SELECT 2 UNION ALL SELECT 3 UNION ALL SELECT 4
              UNION ALL SELECT 5 UNION ALL SELECT 6 UNION ALL SELECT 7 UNION ALL SELECT 8 UNION ALL SELECT 9
              UNION ALL SELECT 10 UNION ALL SELECT 11 UNION ALL SELECT 12 UNION ALL SELECT 13 UNION ALL SELECT 14
              UNION ALL SELECT 15 UNION ALL SELECT 16 UNION ALL SELECT 17 UNION ALL SELECT 18 UNION ALL SELECT 19
              UNION ALL SELECT 20 UNION ALL SELECT 21 UNION ALL SELECT 22 UNION ALL SELECT 23 UNION ALL SELECT 24
              UNION ALL SELECT 25 UNION ALL SELECT 26 UNION ALL SELECT 27 UNION ALL SELECT 28 UNION ALL SELECT 29) AS days
        WHERE strftime('%w', date('2023-11-01', '+' || n || ' day')) = '5'
    ),
    PurchasesAgg AS (
        SELECT
            ((CAST(strftime('%d', p.purchase_date) AS INTEGER) + 6) / 7) AS week_of_month,
            u.membership,
            SUM(p.amount_spend) AS total_amount
        FROM Purchases p
        JOIN Users u ON p.user_id = u.user_id
        WHERE u.membership IN ('Premium', 'VIP')
        GROUP BY week_of_month, membership
    ),
    FridaysMembership AS (
        SELECT
            ((CAST(strftime('%d', f.purchase_date) AS INTEGER) + 6) / 7) AS week_of_month,
            m.membership
        FROM Fridays f
        CROSS JOIN (SELECT 'Premium' AS membership UNION ALL SELECT 'VIP') m
    )
    SELECT 
        fm.week_of_month,
        fm.membership,
        COALESCE(pa.total_amount, 0) AS total_amount
    FROM FridaysMembership fm
    LEFT JOIN PurchasesAgg pa
    ON fm.week_of_month = pa.week_of_month AND fm.membership = pa.membership
    ORDER BY fm.week_of_month, fm.membership;
    `
    return db.Query(query)
}

Explanation: The Go version mirrors the Python version but uses database/sql to execute the query. SQLite3 is assumed, but the query logic is identical. The use of COALESCE ensures missing values default to 0.

Worked Examples

For the sample input:

• Week 1 Friday is 2023-11-03. Premium member 11 spent 1126. VIP no purchase. Output: (1, Premium, 1126), (1, VIP, 0)
• Week 2 Friday is 2023-11-10. VIP member 15 spent 7473. Premium no purchase. Output: (2, Premium, 0), (2, VIP, 7473)
• Week 3 Friday is 2023