LeetCode 2994 - Friday Purchases II

The problem requires calculating the total spending by users on each Friday in November 2023, broken down by week of the month. The input is a Purchases table containing userid, purchasedate, and amountspend.

leetcodeharddatabase

LeetCode Problem 2994

Difficulty: 🔴 Hard
Topics: Database

Solution

Problem Understanding

The problem requires calculating the total spending by users on each Friday in November 2023, broken down by week of the month. The input is a Purchases table containing user_id, purchase_date, and amount_spend. The output must include all Fridays in November, and for any Friday with no purchases, the total should be reported as 0. The results must be ordered by the week of the month in ascending order.

Key constraints are:

  1. purchase_date ranges from 2023-11-01 to 2023-11-30.
  2. Each row is uniquely identified by (user_id, purchase_date, amount_spend).
  3. A "week of the month" is determined by the Friday in that week (e.g., first Friday is week 1).

Edge cases include Fridays with no purchases, weeks where multiple purchases occur on the same Friday, and handling the first and last week correctly even if they are partial weeks. The input is relatively small, limited to one month, so computational performance is not a major concern, but correct handling of missing Fridays is crucial.

Approaches

The brute-force approach would involve iterating over all days in November, checking if each day is a Friday, then summing all purchases for that day. If there are no purchases, we manually insert 0. This approach works but is verbose and requires maintaining a mapping of dates to week numbers.

The optimal approach leverages SQL date functions or Python/Go date libraries to directly filter Fridays and compute the week of the month. Specifically, we:

  1. Identify Fridays in November.
  2. Compute the week of the month for each Friday.
  3. Aggregate purchases for each Friday and default missing Fridays to 0.
  4. Return results sorted by week of the month.

The key insight is that we only need to consider Fridays, reducing unnecessary computation and ensuring missing weeks are accounted for.

Approach Time Complexity Space Complexity Notes
Brute Force O(n*D) O(D) Iterate over all dates and purchases, sum manually, fill zeros for missing Fridays
Optimal O(n) O(F) Filter Fridays, group by week, aggregate, insert zeros for missing weeks, D = days in month, F = number of Fridays

Algorithm Walkthrough

  1. Generate a list of all Fridays in November 2023. Use the fact that November 3, 2023 is a Friday and increment by 7 days.
  2. Compute the week of the month for each Friday. This is calculated as (day_of_month - 1) // 7 + 1.
  3. Aggregate the Purchases table by purchase_date, summing amount_spend.
  4. Join the aggregated results with the list of Fridays, filling in 0 where no purchase exists.
  5. Sort the final result by week_of_month.

Why it works: By explicitly generating all Fridays and computing their week numbers, we ensure every week is represented, even if there were no purchases. Aggregation ensures multiple purchases on the same Friday are summed correctly.

Python Solution

from typing import List
import datetime

class Solution:
    def fridayPurchases(self, Purchases: List[dict]) -> List[dict]:
        # Step 1: Generate all Fridays in November 2023
        start_date = datetime.date(2023, 11, 1)
        end_date = datetime.date(2023, 11, 30)
        fridays = []
        current = start_date
        while current.weekday() != 4:  # Friday is 4
            current += datetime.timedelta(days=1)
        while current <= end_date:
            week_of_month = (current.day - 1) // 7 + 1
            fridays.append({"purchase_date": current, "week_of_month": week_of_month})
            current += datetime.timedelta(days=7)

        # Step 2: Aggregate purchases by date
        total_spend = {}
        for row in Purchases:
            date = datetime.datetime.strptime(row["purchase_date"], "%Y-%m-%d").date()
            total_spend[date] = total_spend.get(date, 0) + row["amount_spend"]

        # Step 3: Prepare final output
        result = []
        for friday in fridays:
            date = friday["purchase_date"]
            result.append({
                "week_of_month": friday["week_of_month"],
                "purchase_date": str(date),
                "total_amount": total_spend.get(date, 0)
            })

        return result

The implementation first generates all Fridays in November, then sums purchases by date. The final step combines the Friday list with aggregated totals, ensuring missing Fridays are included with zero spending.

Go Solution

package main

import (
    "time"
)

type Purchase struct {
    UserID       int
    PurchaseDate string
    AmountSpend  int
}

type Result struct {
    WeekOfMonth  int
    PurchaseDate string
    TotalAmount  int
}

func FridayPurchases(purchases []Purchase) []Result {
    fridays := []Result{}
    start, _ := time.Parse("2006-01-02", "2023-11-01")
    end, _ := time.Parse("2006-01-02", "2023-11-30")

    // Find first Friday
    current := start
    for current.Weekday() != time.Friday {
        current = current.AddDate(0, 0, 1)
    }

    // Generate all Fridays with week_of_month
    for !current.After(end) {
        week := (current.Day()-1)/7 + 1
        fridays = append(fridays, Result{WeekOfMonth: week, PurchaseDate: current.Format("2006-01-02")})
        current = current.AddDate(0, 0, 7)
    }

    // Aggregate purchases by date
    totals := map[string]int{}
    for _, p := range purchases {
        totals[p.PurchaseDate] += p.AmountSpend
    }

    // Merge totals with Fridays
    for i := range fridays {
        fridays[i].TotalAmount = totals[fridays[i].PurchaseDate]
    }

    return fridays
}

In Go, the approach is nearly identical. We use time.Time to handle dates, a map to aggregate totals, and then fill the results, preserving the zero amounts for Fridays without purchases. Go requires explicit formatting for dates.

Worked Examples

Given the input table:

user_id purchase_date amount_spend
11 2023-11-07 1126
15 2023-11-30 7473
17 2023-11-14 2414
12 2023-11-24 9692
8 2023-11-03 5117
1 2023-11-16 5241
10 2023-11-12 8266
13 2023-11-24 12000

Step 1: Generate Fridays:

week_of_month purchase_date
1 2023-11-03
2 2023-11-10
3 2023-11-17
4 2023-11-24

Step 2: Aggregate purchases:

purchase_date total_amount
2023-11-03 5117
2023-11-07 1126
2023-11-10 0
2023-11-17 0
2023-11-24 21692
2023-11-30 7473

Step 3: Merge Fridays with totals:

week_of_month purchase_date total_amount
1 2023-11-03 5117
2 2023-11-10 0
3 2023-11-17 0
4 2023-11-24 21692

Complexity Analysis

Measure Complexity Explanation
Time O(n) We iterate once through purchases and once through Fridays. n is the number of purchases.
Space O(F) We store a map of totals for each purchase date, and a list of Fridays. F is number of Fridays in November (≈4-5).

The algorithm scales linearly with the number of purchases and has minimal extra space due to the limited number of Fridays in a month.

Test Cases

# Provided example
assert Solution().fridayPurchases([
    {"user_id":11,"purchase_date":"2023-11-07","amount_spend":1126},
    {"user_id":15,"purchase_date":"2023-11-30","amount_spend":7473},
    {"user_id":17,"purchase_date":"2023-11-14","amount_sp