Problem Description

Given a list of invoices, where each invoice contains a list of products and their respective quantities and prices, determine the total worth of each product across all invoices. Each invoice is represented as a list of products, and each product is described by its productId, quantity, and pricePerUnit. The goal is to compute, for every unique product, the sum of (quantity × pricePerUnit) over all invoices in which it appears.

• Each product may appear in multiple invoices.
• Do not reuse or double-count product entries within the same invoice.
• Return the total worth for each product, typically as a mapping from productId to its total worth.

Thought Process

To solve this problem, first consider a brute-force approach: for every invoice, inspect each product and calculate its contribution to the total worth. For each product, sum up its worth across all invoices. This can be done by iterating through every invoice and every product within, then accumulating the total for each productId.

However, this approach can be inefficient if there are many invoices and products. To optimize, we can use a hash map (dictionary) to store the running total for each product as we process the invoices. This way, we avoid unnecessary repeated searches and make our lookups and updates efficient.

The key insight is mapping each productId to its cumulative worth as we process each invoice entry. This is a classic aggregation pattern.

Solution Approach

Let's break down the steps for an efficient solution:

1. Initialize a hash map: Create an empty dictionary (or map) to store the total worth for each productId.
2. Iterate through invoices: For each invoice in the input list, process its products.
3. Process each product: For each product in an invoice, extract its productId, quantity, and pricePerUnit. Compute the product's worth for this invoice as quantity × pricePerUnit.
4. Aggregate worth: Add this value to the running total for the corresponding productId in the hash map. If the product is not yet in the map, initialize its total to zero before adding.
5. Return the result: After processing all invoices, return the hash map containing each productId and its total worth.

This approach ensures each product's worth is computed efficiently, with O(1) updates per product.

Example Walkthrough

Suppose we have the following invoices:

    invoices = [
      [ {'productId': 1, 'quantity': 2, 'pricePerUnit': 10},
        {'productId': 2, 'quantity': 1, 'pricePerUnit': 20} ],
      [ {'productId': 1, 'quantity': 3, 'pricePerUnit': 10},
        {'productId': 3, 'quantity': 5, 'pricePerUnit': 5} ]
    ]
  

Step by step:

• First invoice:
  • Product 1: 2 × 10 = 20 (add to map: {1: 20})
  • Product 2: 1 × 20 = 20 (add to map: {1: 20, 2: 20})
• Second invoice:
  • Product 1: 3 × 10 = 30 (add to map: {1: 50, 2: 20})
  • Product 3: 5 × 5 = 25 (add to map: {1: 50, 2: 20, 3: 25})

Final output: {1: 50, 2: 20, 3: 25}

Code Implementation

def productsWorthOverInvoices(invoices):
    product_totals = {}
    for invoice in invoices:
        for product in invoice:
            pid = product['productId']
            qty = product['quantity']
            price = product['pricePerUnit']
            worth = qty * price
            if pid not in product_totals:
                product_totals[pid] = 0
            product_totals[pid] += worth
    return product_totals
      

#include <vector>
#include <unordered_map>
using namespace std;

struct Product {
    int productId;
    int quantity;
    int pricePerUnit;
};

unordered_map<int, int> productsWorthOverInvoices(const vector<vector<Product>>& invoices) {
    unordered_map<int, int> productTotals;
    for (const auto& invoice : invoices) {
        for (const auto& product : invoice) {
            int worth = product.quantity * product.pricePerUnit;
            productTotals[product.productId] += worth;
        }
    }
    return productTotals;
}
      

import java.util.*;

class Product {
    int productId;
    int quantity;
    int pricePerUnit;
    Product(int productId, int quantity, int pricePerUnit) {
        this.productId = productId;
        this.quantity = quantity;
        this.pricePerUnit = pricePerUnit;
    }
}

public class Solution {
    public Map<Integer, Integer> productsWorthOverInvoices(List<List<Product>> invoices) {
        Map<Integer, Integer> productTotals = new HashMap<>();
        for (List<Product> invoice : invoices) {
            for (Product product : invoice) {
                int worth = product.quantity * product.pricePerUnit;
                productTotals.put(product.productId, productTotals.getOrDefault(product.productId, 0) + worth);
            }
        }
        return productTotals;
    }
}
      

function productsWorthOverInvoices(invoices) {
    const productTotals = {};
    for (const invoice of invoices) {
        for (const product of invoice) {
            const pid = product.productId;
            const worth = product.quantity * product.pricePerUnit;
            if (!(pid in productTotals)) {
                productTotals[pid] = 0;
            }
            productTotals[pid] += worth;
        }
    }
    return productTotals;
}
      

Time and Space Complexity

• Brute-force approach: If you used a nested loop with extra searching per product, time complexity could be O(N × M), where N is the number of invoices and M is the average number of products per invoice, plus extra time for searching and updating results.
• Optimized approach: Our solution visits each product exactly once, so time complexity is O(T), where T is the total number of product entries across all invoices. All hash map operations (insert, update, lookup) are O(1) on average.
• Space complexity: O(P), where P is the number of unique product IDs, since we store one entry per product in the hash map.

Summary

We tackled the problem by recognizing it as an aggregation task, using a hash map to efficiently sum the worth of each product across all invoices. By iterating through every product entry and updating a running total, we achieve an optimal O(T) solution. The key insight is to avoid repeated searches and leverage fast hash map operations, resulting in simple, readable, and efficient code.