Generate the Invoice

Problem

Table: Products

+-------------+------+
| Column Name | Type |
+-------------+------+
| product_id  | int  |
| price       | int  |
+-------------+------+
product_id contains unique values.
Each row in this table shows the ID of a product and the price of one unit.

Table: Purchases

+-------------+------+
| Column Name | Type |
+-------------+------+
| invoice_id  | int  |
| product_id  | int  |
| quantity    | int  |
+-------------+------+
(invoice_id, product_id) is the primary key (combination of columns with unique values) for this table.
Each row in this table shows the quantity ordered from one product in an invoice.

Write a solution to show the details of the invoice with the highest price. If two or more invoices have the same price, return the details of the one with the smallest invoice_id.

Return the result table in any order.

The result format is shown in the following example.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


Input: 
Products table:
+------------+-------+
| product_id | price |
+------------+-------+
| 1          | 100   |
| 2          | 200   |
+------------+-------+
Purchases table:
+------------+------------+----------+
| invoice_id | product_id | quantity |
+------------+------------+----------+
| 1          | 1          | 2        |
| 3          | 2          | 1        |
| 2          | 2          | 3        |
| 2          | 1          | 4        |
| 4          | 1          | 10       |
+------------+------------+----------+
Output: 
+------------+----------+-------+
| product_id | quantity | price |
+------------+----------+-------+
| 2          | 3        | 600   |
| 1          | 4        | 400   |
+------------+----------+-------+
Explanation: 
Invoice 1: price = (2 * 100) = $200
Invoice 2: price = (4 * 100) + (3 * 200) = $1000
Invoice 3: price = (1 * 200) = $200
Invoice 4: price = (10 * 100) = $1000
The highest price is $1000, and the invoices with the highest prices are 2 and 4. We return the details of the one with the smallest ID, which is invoice 2.

Solution

Method 1 – Join, Group, and Aggregate for Invoice Generation

Intuition

To generate the invoice, we need to join purchases with product prices, group by invoice and product, and sum the quantities and total price for each product in each invoice. Then, sum the total for each invoice.

Approach

Join Purchases with Products on product_id to get the price for each purchase.
Group by invoice_id and product_id to sum the quantity and calculate the total price for each product in each invoice.
For each invoice, sum the total price of all products to get the invoice total.
Output the invoice details: invoice_id, product_id, quantity, product_total, and invoice_total, ordered by invoice_id and product_id.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


WITH invoice_details AS (
  SELECT p.invoice_id, p.product_id, SUM(p.quantity) AS quantity,
         SUM(p.quantity * pr.price) AS product_total
  FROM Purchases p
  JOIN Products pr ON p.product_id = pr.product_id
  GROUP BY p.invoice_id, p.product_id
),
invoice_totals AS (
  SELECT invoice_id, SUM(product_total) AS invoice_total
  FROM invoice_details
  GROUP BY invoice_id
)
SELECT d.invoice_id, d.product_id, d.quantity, d.product_total, t.invoice_total
FROM invoice_details d
JOIN invoice_totals t ON d.invoice_id = t.invoice_id
ORDER BY d.invoice_id, d.product_id;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


WITH invoice_details AS (
  SELECT p.invoice_id, p.product_id, SUM(p.quantity) AS quantity,
         SUM(p.quantity * pr.price) AS product_total
  FROM Purchases p
  JOIN Products pr ON p.product_id = pr.product_id
  GROUP BY p.invoice_id, p.product_id
),
invoice_totals AS (
  SELECT invoice_id, SUM(product_total) AS invoice_total
  FROM invoice_details
  GROUP BY invoice_id
)
SELECT d.invoice_id, d.product_id, d.quantity, d.product_total, t.invoice_total
FROM invoice_details d
JOIN invoice_totals t ON d.invoice_id = t.invoice_id
ORDER BY d.invoice_id, d.product_id;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution:
    def generate_invoice(self, products: 'pd.DataFrame', purchases: 'pd.DataFrame') -> 'pd.DataFrame':
        import pandas as pd
        df = purchases.merge(products, on='product_id')
        details = df.groupby(['invoice_id', 'product_id'], as_index=False).agg(
            quantity=('quantity', 'sum'),
            product_total=('quantity', lambda x: (x * df.loc[x.index, 'price']).sum())
        )
        invoice_totals = details.groupby('invoice_id', as_index=False)['product_total'].sum().rename(columns={'product_total': 'invoice_total'})
        result = details.merge(invoice_totals, on='invoice_id')
        return result.sort_values(['invoice_id', 'product_id']).reset_index(drop=True)

Complexity

⏰ Time complexity: O(n + m), where n is the number of purchases and m is the number of products, since each record is processed once.
🧺 Space complexity: O(n + m), for storing intermediate and output tables.

Problem#

Examples#

Solution#

Method 1 – Join, Group, and Aggregate for Invoice Generation#

Intuition#

Approach#

Code#

Complexity#