LeetCode Problem 2362

Difficulty: 🔴 Hard
Topics: Database

Solution

LeetCode 2362 - Generate the Invoice

Problem Understanding

This is a SQL database problem involving two tables:

Products

product_id	price
Unique product identifier	Unit price of the product

Purchases

invoice_id	product_id	quantity
Invoice identifier	Product purchased	Number of units purchased

Each row in Purchases represents one product included in an invoice. Since (invoice_id, product_id) is the primary key, the same product cannot appear twice within the same invoice.

The total value of an invoice is computed by summing:

$$\text{quantity} \times \text{price}$$

for every product included in that invoice.

The task consists of two parts:

1. Compute the total price of every invoice.
2. Find the invoice with the highest total price.

• If multiple invoices have the same maximum price, choose the one with the smallest invoice_id.

3. Return all product lines belonging to that selected invoice.
4. For each returned product, output:

• product_id
• quantity
• price, where price = quantity × unit_price

The output may be returned in any order.

Example Interpretation

For invoice 2:

product_id	quantity	unit price
1	4	100
2	3	200

The line totals are:

• Product 1: 4 × 100 = 400
• Product 2: 3 × 200 = 600

Invoice total:

400 + 600 = 1000

If this is the highest invoice value, these two rows become the output.

Important Edge Cases

A few cases can easily introduce bugs:

• Multiple invoices may share the same maximum total value. The smallest invoice_id must be selected.
• An invoice may contain only one product.
• Different invoices may have identical totals but different numbers of products.
• The returned rows must contain line-item prices (quantity × unit_price), not the invoice total.
• The output ordering is unspecified, so sorting is unnecessary.

Because this is a database problem, efficiency comes from using aggregation and joins rather than procedural iteration.

Approaches

Brute Force Approach

A straightforward solution would be:

1. Join Purchases and Products.
2. Compute every line-item cost.
3. Group by invoice and calculate invoice totals.
4. Scan all invoices to find the largest total.
5. Handle ties by selecting the smallest invoice ID.
6. Query the chosen invoice again to retrieve its line items.

This approach is logically correct because it explicitly computes every invoice total before selecting the best candidate.

However, writing separate intermediate computations and repeatedly processing the same data is unnecessary. SQL aggregation can perform these operations more elegantly in a single query structure.

Key Insight

The important observation is that invoice totals can be computed directly using:

SUM(quantity * price)

grouped by invoice_id.

Once we have invoice totals:

• Sort by total price descending.
• Sort by invoice ID ascending to break ties.
• Take the first invoice.

After identifying that invoice, join back to the purchase rows and compute each product's contribution:

quantity * price

This naturally produces the required output.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(P)	O(P)	Multiple logical passes over purchase records
Optimal	O(P)	O(P)	Aggregation and selection performed directly in SQL
Where P = number of purchase rows

Algorithm Walkthrough

Optimal SQL Algorithm

1. Join Purchases and Products using product_id.

This provides access to both the purchased quantity and the unit price needed to calculate costs. 2. Group the joined rows by invoice_id.

For each invoice, compute:

SUM(quantity * price)

which gives the total invoice value. 3. Order the invoice totals.

Sort by:

• total value descending
• invoice ID ascending

This guarantees that the highest-value invoice appears first, and ties are resolved using the smallest invoice ID. 4. Select the first invoice.

This becomes the target invoice whose details must be returned. 5. Join the selected invoice back to the original purchase rows.

Retrieve all products belonging to that invoice. 6. Compute each line-item price.

For every product in the chosen invoice:

quantity * unit_price

7. Return:

• product_id
• quantity
• computed line-item price

Why it works

The grouping step computes the exact total value of every invoice. Ordering by total value descending guarantees that the maximum invoice appears before all others. Ordering by invoice ID ascending ensures that when multiple invoices share the same total value, the smallest invoice ID is chosen. Once the correct invoice is identified, returning all rows belonging to that invoice produces exactly the output required by the problem.

SQL Solution

WITH invoice_totals AS (
    SELECT
        p.invoice_id,
        SUM(p.quantity * pr.price) AS total_price
    FROM Purchases p
    JOIN Products pr
        ON p.product_id = pr.product_id
    GROUP BY p.invoice_id
),
best_invoice AS (
    SELECT invoice_id
    FROM invoice_totals
    ORDER BY total_price DESC, invoice_id ASC
    LIMIT 1
)
SELECT
    p.product_id,
    p.quantity,
    p.quantity * pr.price AS price
FROM Purchases p
JOIN Products pr
    ON p.product_id = pr.product_id
JOIN best_invoice b
    ON p.invoice_id = b.invoice_id;

Implementation Explanation

The first common table expression, invoice_totals, calculates the total monetary value of every invoice. This is done by joining each purchase row with its product price and summing quantity * price for each invoice.

The second common table expression, best_invoice, selects the invoice that should be returned. The invoices are sorted by total value in descending order so the highest-valued invoice appears first. The secondary ordering by invoice ID ensures correct tie breaking.

Finally, the chosen invoice is joined back with the purchase records and product prices. For every purchased product, the query computes the line-item price using quantity * unit_price and returns the required columns.

Worked Example

Example 1

Products:

product_id	price
1	100
2	200

Purchases:

invoice_id	product_id	quantity
1	1	2
3	2	1
2	2	3
2	1	4
4	1	10

Step 1: Compute Invoice Totals

After joining prices:

invoice_id	product_id	quantity	unit price	line total
1	1	2	100	200
3	2	1	200	200
2	2	3	200	600
2	1	4	100	400
4	1	10	100	1000

Step 2: Aggregate by Invoice

invoice_id	total
1	200
2	1000
3	200
4	1000

Step 3: Sort

invoice_id	total
2	1000
4	1000
1	200
3	200

Invoice 2 appears first because it has the same total as invoice 4 but a smaller ID.

Step 4: Return Invoice 2 Details

product_id	quantity	price
2	3	600
1	4	400

This matches the expected output.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(P)	Join and aggregation process each purchase row once
Space	O(P)	Intermediate aggregation results may store invoice totals
Where P = number of purchase rows

The dominant work is the join between Purchases and Products followed by the aggregation by invoice. Modern database engines typically implement these operations efficiently using hashing or sorting, resulting in linear processing relative to the number of purchase records.

Test Cases

-- Example from the statement
Products:
(1,100)
(2,200)

Purchases:
(1,1,2)
(3,2,1)
(2,2,3)
(2,1,4)
(4,1,10)

-- Expected:
-- (2,3,600)
-- (1,4,400)

-- Single invoice
Products:
(1,50)

Purchases:
(1,1,5)

-- Expected:
-- (1,5,250)

-- Tie on invoice total, smaller invoice_id wins
Products:
(1,100)

Purchases:
(1,1,10)
(2,1,10)

-- Expected:
-- invoice 1 returned

-- Invoice with multiple products beats single-product invoice
Products:
(1,100)
(2,300)

Purchases:
(1,1,2)
(1,2,2)
(2,2,1)

-- Invoice 1 total = 800
-- Invoice 2 total = 300
-- Expected:
-- invoice 1 rows

-- Multiple invoices with equal totals and different compositions
Products:
(1,100)
(2,200)

Purchases:
(1,1,4)
(2,2,2)

-- Both totals = 400
-- Expected:
-- invoice 1 rows

Test Summary

Test	Why
Problem example	Validates normal operation and tie handling
Single invoice	Smallest possible meaningful input
Equal maximum totals	Verifies invoice ID tie breaker
Multi-product invoice	Verifies aggregation across products
Different compositions, same total	Confirms totals determine winner, not row count

Edge Cases

Multiple Invoices Share the Maximum Total

This is the most important edge case in the problem. A solution that only finds the maximum invoice value may return any matching invoice. The problem explicitly requires selecting the smallest invoice_id. The ORDER BY total_price DESC, invoice_id ASC clause guarantees correct tie resolution.

Invoice Contains Only One Product

Some invoices may consist of a single purchase row. The aggregation still works correctly because the invoice total becomes the value of that single line item. No special handling is required.

Different Numbers of Products per Invoice

One invoice may contain many products while another contains only one. The winner is determined solely by the sum of all line-item values. The grouping operation correctly accumulates all products belonging to the same invoice before comparison.

Returned Price Is a Line-Item Price

A common mistake is returning the invoice total for every row. The output requires the price contribution of each product within the selected invoice. Computing quantity * unit_price in the final query ensures the correct value is returned for every row.