LeetCode 2329 - Product Sales Analysis V

This problem asks us to calculate how much money each user has spent across all of their purchases. We are given two database tables: The Sales table stores purchase records.

leetcodeeasydatabase

LeetCode Problem 2329

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

This problem asks us to calculate how much money each user has spent across all of their purchases.

We are given two database tables:

The Sales table stores purchase records. Each row represents a transaction involving a specific product bought by a user, along with the quantity purchased.

The Product table stores the price of each product.

To compute a user's total spending, we must combine information from both tables. For every row in Sales, we determine the cost of that purchase by multiplying:

quantity × product price

Then we sum all purchase costs belonging to the same user.

The output should contain:

  • user_id
  • spending, which is the total amount that user spent

The results must be ordered:

  1. By spending in descending order
  2. If two users spent the same amount, by user_id in ascending order

The important observation is that the Sales table does not contain prices directly, so we must join it with the Product table using product_id.

The problem guarantees that every product_id in Sales exists in Product, because product_id is a foreign key. This means we never need to handle missing prices.

Even though this is labeled as an Easy database problem, it still tests several important SQL concepts:

  • Table joins
  • Aggregation with SUM
  • Grouping with GROUP BY
  • Multi-level sorting with ORDER BY

Some important edge cases include users purchasing the same product multiple times, users having equal total spending, and products appearing in many sales rows. A naive implementation that does not aggregate properly could produce duplicate rows or incorrect totals.

Approaches

Brute Force Approach

A brute-force approach would conceptually process each user independently.

For every user, we could scan the entire Sales table to find all of their purchases. For each purchase, we would then scan the Product table to find the corresponding product price. After computing the cost of every purchase, we would sum them together.

This approach is correct because it explicitly computes every transaction cost and accumulates totals per user. However, it is inefficient because the Product table is repeatedly searched for matching prices.

If there are:

  • S sales rows
  • P product rows
  • U users

then repeatedly scanning tables leads to unnecessary repeated work.

Optimal Approach

The optimal solution uses a SQL JOIN to combine sales information with product prices in a single operation.

After joining:

  • each sales row already contains its product price
  • we can compute quantity * price
  • then aggregate totals per user using SUM
  • finally sort the results according to the required ordering

The key insight is that relational databases are optimized for joins and aggregations. Instead of manually searching for matching products repeatedly, the database engine efficiently matches rows using indexed relationships.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(S × P) O(U) Repeatedly scans product table for every sale
Optimal O(S + P) O(U) Uses join and aggregation efficiently

Algorithm Walkthrough

Optimal SQL Algorithm

  1. Start with the Sales table because it contains all purchase transactions.
  2. Join the Sales table with the Product table using product_id.

This step is necessary because the sales data only tells us how many units were purchased, while the product table tells us the price of each unit. 3. For every joined row, compute the transaction cost:

quantity × price

This gives the amount spent for that individual purchase. 4. Group all rows by user_id.

Grouping ensures that all purchases belonging to the same user are collected together. 5. Use SUM(quantity * price) to calculate total spending for each user. 6. Sort the results:

  • first by spending in descending order
  • then by user_id in ascending order for tie-breaking
  1. Return the final table containing:
  • user_id
  • spending

Why it works

The algorithm works because every sales row contributes exactly one purchase cost to exactly one user. The join guarantees that each purchase receives the correct product price. Grouping by user_id ensures all purchases for the same user are accumulated together, and summing the transaction costs produces the correct total spending.

Python Solution

Although this is a database problem and normally solved using SQL, the equivalent logic can be demonstrated in Python for clarity.

from collections import defaultdict
from typing import List, Dict

class Solution:
    def productSalesAnalysis(
        self,
        sales: List[List[int]],
        products: List[List[int]]
    ) -> List[List[int]]:
        
        price_map: Dict[int, int] = {}

        for product_id, price in products:
            price_map[product_id] = price

        spending_map = defaultdict(int)

        for sale_id, product_id, user_id, quantity in sales:
            spending_map[user_id] += quantity * price_map[product_id]

        result = []

        for user_id, spending in spending_map.items():
            result.append([user_id, spending])

        result.sort(key=lambda x: (-x[1], x[0]))

        return result

The implementation first builds a hash map from product_id to price. This allows constant-time price lookups.

Next, the code iterates through every sales row. For each transaction, it multiplies the purchased quantity by the product price and adds the result to that user's cumulative spending.

After processing all transactions, the result list is sorted according to the problem requirements:

  • descending spending
  • ascending user ID for ties

This mirrors the exact logic used in the SQL solution.

SQL Solution

SELECT
    s.user_id,
    SUM(s.quantity * p.price) AS spending
FROM Sales s
JOIN Product p
    ON s.product_id = p.product_id
GROUP BY s.user_id
ORDER BY spending DESC, s.user_id ASC;

This query performs the entire computation directly inside the database engine.

Go Solution

package main

import (
	"sort"
)

type Result struct {
	UserID  int
	Spending int
}

func productSalesAnalysis(sales [][]int, products [][]int) [][]int {
	priceMap := make(map[int]int)

	for _, product := range products {
		productID := product[0]
		price := product[1]
		priceMap[productID] = price
	}

	spendingMap := make(map[int]int)

	for _, sale := range sales {
		productID := sale[1]
		userID := sale[2]
		quantity := sale[3]

		spendingMap[userID] += quantity * priceMap[productID]
	}

	result := [][]int{}

	for userID, spending := range spendingMap {
		result = append(result, []int{userID, spending})
	}

	sort.Slice(result, func(i, j int) bool {
		if result[i][1] == result[j][1] {
			return result[i][0] < result[j][0]
		}
		return result[i][1] > result[j][1]
	})

	return result
}

The Go implementation follows the same logic as the Python version.

A Go map is used for constant-time product price lookup and cumulative spending aggregation. Since Go does not provide built-in tuple sorting like Python, sort.Slice is used with a custom comparator function.

Go integer arithmetic is sufficient here because the constraints are small enough that standard integer types safely handle the multiplication and summation operations.

Worked Examples

Example 1

Input:

Sales:
[1,1,101,10]
[2,2,101,1]
[3,3,102,3]
[4,3,102,2]
[5,2,103,3]

Product:
[1,10]
[2,25]
[3,15]

Step 1: Build Product Price Map

product_id price
1 10
2 25
3 15

Resulting map:

{
    1: 10,
    2: 25,
    3: 15
}

Step 2: Process Sales Rows

sale_id product_id user_id quantity price cost cumulative spending
1 1 101 10 10 100 101 → 100
2 2 101 1 25 25 101 → 125
3 3 102 3 15 45 102 → 45
4 3 102 2 15 30 102 → 75
5 2 103 3 25 75 103 → 75

Final spending map:

{
    101: 125,
    102: 75,
    103: 75
}

Step 3: Sort Results

Before sorting:

[
    [101, 125],
    [102, 75],
    [103, 75]
]

After sorting:

[
    [101, 125],
    [102, 75],
    [103, 75]
]

Users 102 and 103 have equal spending, so the smaller user_id comes first.

Complexity Analysis

Measure Complexity Explanation
Time O(S + P) One pass through products and one pass through sales
Space O(U + P) Stores product prices and user spending totals

The algorithm performs a single traversal of the product table to build the price lookup structure and a single traversal of the sales table to compute totals. Sorting the final users adds O(U log U) time, where U is the number of users.

In practice, the dominant work comes from processing sales rows and sorting user totals.

Test Cases

def solve(sales, products):
    from collections import defaultdict

    price_map = {}

    for product_id, price in products:
        price_map[product_id] = price

    spending_map = defaultdict(int)

    for _, product_id, user_id, quantity in sales:
        spending_map[user_id] += quantity * price_map[product_id]

    result = [[user_id, spending] for user_id, spending in spending_map.items()]

    result.sort(key=lambda x: (-x[1], x[0]))

    return result

# Example case
assert solve(
    [
        [1, 1, 101, 10],
        [2, 2, 101, 1],
        [3, 3, 102, 3],
        [4, 3, 102, 2],
        [5, 2, 103, 3]
    ],
    [
        [1, 10],
        [2, 25],
        [3, 15]
    ]
) == [
    [101, 125],
    [102, 75],
    [103, 75]
]  # basic example from problem statement

# Single user with multiple purchases
assert solve(
    [
        [1, 1, 1, 2],
        [2, 2, 1, 3]
    ],
    [
        [1, 5],
        [2, 10]
    ]
) == [
    [1, 40]
]  # verifies aggregation across multiple products

# Multiple users with equal spending
assert solve(
    [
        [1, 1, 1, 2],
        [2, 2, 2, 1]
    ],
    [
        [1, 10],
        [2, 20]
    ]
) == [
    [1, 20],
    [2, 20]
]  # verifies tie-breaking by user_id

# Same product purchased multiple times
assert solve(
    [
        [1, 1, 1, 1],
        [2, 1, 1, 2],
        [3, 1, 2, 1]
    ],
    [
        [1, 7]
    ]
) == [
    [1, 21],
    [2, 7]
]  # verifies repeated product handling

# Large quantity values
assert solve(
    [
        [1, 1, 1, 1000]
    ],
    [
        [1, 999]
    ]
) == [
    [1, 999000]
]  # verifies multiplication correctness

Test Summary

Test Why
Problem statement example Verifies overall correctness
Single user multiple products Ensures aggregation works correctly
Equal spending users Verifies tie-breaking rules
Repeated product purchases Ensures cumulative additions work
Large quantity values Verifies multiplication and accumulation

Edge Cases

Multiple Users With Identical Spending

One subtle case occurs when two or more users spend exactly the same amount. A solution that only sorts by spending could produce inconsistent ordering. The implementation handles this by adding a secondary sort condition using user_id in ascending order.

Same Product Purchased Multiple Times

A user may buy the same product in several different transactions. An incorrect implementation might overwrite previous totals instead of accumulating them. The solution correctly adds every transaction cost into the user's running total.

Single Product Table Entry Used Many Times

The same product may appear in many sales rows. Repeatedly searching for its price would be inefficient in a brute-force solution. The optimized implementation avoids this by storing prices in a hash map for constant-time lookup.

Single User in the Entire Dataset

If only one user exists, the grouping logic must still work correctly and return exactly one row. Since the algorithm aggregates dynamically using a map, it naturally handles this scenario without requiring any special-case logic.