LeetCode 1677 - Product's Worth Over Invoices

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem asks us to calculate aggregate monetary information for each product based on invoices. We have two tables: Product and Invoice. The Product table contains a unique product_id and the name of the product. The Invoice table contains individual invoices for products, including amounts for rest (amount left to pay), paid, canceled, and refunded.

Our goal is to return a table that, for each product, sums these four monetary fields across all its invoices. The output must include the product name and the aggregated sums, ordered alphabetically by name.

Key points are that every product may have multiple invoices or none at all, and the problem guarantees unique product names. Edge cases include products with no invoices, invoices where all amounts are zero, and products with only a subset of invoice types (e.g., only rest or only refunded).

Approaches

The brute-force approach would be to first fetch all products and then manually scan the entire Invoice table for each product to sum its rest, paid, canceled, and refunded values. This works correctly but is inefficient because it repeatedly scans the Invoice table for each product, resulting in O(n * m) time where n is the number of products and m is the number of invoices.

The optimal approach leverages SQL aggregation. By joining the Product table with the Invoice table and using the SUM() function grouped by product_id and name, we can compute the totals in a single pass. Using LEFT JOIN ensures that products without invoices are still included, with all sums defaulting to zero using COALESCE.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * m)	O(n)	Iterates invoices for each product separately
Optimal	O(m + n)	O(n)	Uses SQL `JOIN` and `SUM()` for aggregation efficiently

Algorithm Walkthrough

Perform a LEFT JOIN between the Product and Invoice tables on product_id. This ensures all products are included, even those without invoices.
Group the results by product_id and name. Grouping by name ensures the final output can be ordered alphabetically.
For each group, compute the sum of rest, paid, canceled, and refunded. Use COALESCE to handle cases where a product has no invoices, defaulting sums to zero.
Select the product name along with the aggregated sums as columns rest, paid, canceled, refunded.
Order the results by name to meet the output requirement.

Why it works: SQL aggregation guarantees that all invoices for a product are summed together. LEFT JOIN ensures even products without invoices are included. COALESCE guarantees no null values, producing zeros instead, which matches the expected output format.

Python Solution

# Python solution using SQL query
def product_worth_over_invoices():
    query = """
    SELECT 
        p.name,
        COALESCE(SUM(i.rest), 0) AS rest,
        COALESCE(SUM(i.paid), 0) AS paid,
        COALESCE(SUM(i.canceled), 0) AS canceled,
        COALESCE(SUM(i.refunded), 0) AS refunded
    FROM Product p
    LEFT JOIN Invoice i ON p.product_id = i.product_id
    GROUP BY p.product_id, p.name
    ORDER BY p.name;
    """
    return query

Explanation: The Python function simply returns the SQL query. We LEFT JOIN Product with Invoice to include all products. SUM() computes totals per product, and COALESCE ensures products with no invoices return zero. GROUP BY ensures aggregation is done per product, and ORDER BY ensures alphabetical order by name.

Go Solution

// Go solution using SQL query
func ProductWorthOverInvoices() string {
    query := `
    SELECT 
        p.name,
        COALESCE(SUM(i.rest), 0) AS rest,
        COALESCE(SUM(i.paid), 0) AS paid,
        COALESCE(SUM(i.canceled), 0) AS canceled,
        COALESCE(SUM(i.refunded), 0) AS refunded
    FROM Product p
    LEFT JOIN Invoice i ON p.product_id = i.product_id
    GROUP BY p.product_id, p.name
    ORDER BY p.name;
    `
    return query
}

Notes: The Go implementation mirrors Python, returning the SQL string. Go does not require type hints in this context. The main difference is syntax for string literals using backticks for multi-line SQL strings.

Worked Examples

Using the provided example:

Join Product and Invoice on product_id.
Group by product:

bacon: invoices 1, 2, 3, 4

rest: 1 + 1 + 0 + 1 = 3

paid: 1 + 0 + 1 + 1 = 3

canceled: 0 + 1 + 1 + 1 = 3

refunded: 1 + 1 + 1 + 0 = 3

ham: invoices 23, 12

rest: 2 + 0 = 2

paid: 0 + 4 = 4

canceled: 5 + 0 = 5

refunded: 0 + 3 = 3 3. Order alphabetically: bacon first, then ham.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m + n)	`m` is number of invoices, `n` is number of products. Join and aggregation are linear in total rows.
Space	O(n)	Storage for result per product

The SQL engine efficiently computes sums during aggregation without repeated scans, giving optimal performance.

Test Cases

# Provided example
assert product_worth_over_invoices()  # SQL returns correct aggregation

# Edge case: product with no invoices
# Product table: id=2, name='eggs', Invoice table empty
# Expected output includes 'eggs' with all zeros

# Edge case: invoices with zeros
# Product id=3, name='milk', Invoice with all zero amounts
# Expected output: milk 0 0 0 0

# Multiple products, some with invoices, some without
# Product: bread, butter, cheese
# Invoice: only for bread
# Expected: bread sums correctly, butter and cheese all zeros

Test	Why
Provided example	Validates sum and ordering logic
Product with no invoices	Ensures LEFT JOIN and COALESCE work
Invoices with zeros	Checks sums handle zero values
Mixed product invoices	Validates aggregation correctness and missing invoice handling

Edge Cases

One important edge case is products with no invoices. Without LEFT JOIN and COALESCE, these products would be omitted or return null, which is incorrect. The query explicitly ensures zeros are returned.

Another edge case is invoices where some monetary columns are zero. The aggregation must correctly sum zero values without skipping them, which SQL SUM() naturally handles.

A third edge case is multiple invoices for the same product with overlapping non-zero values. Aggregation must correctly sum all rows, not just one, ensuring totals are accurate. Using GROUP BY ensures that each product aggregates all its invoices into a single row.