Problem Description

You are given data about the prices of products at different stores. For each product, you want to find out its price at every store. The data is provided as a list of records, where each record contains a product name, a store name, and the price of that product at that store.

Your task is to generate a mapping for each store that shows the price of every product available at that store. If a product is not sold at a particular store, it should be omitted from that store's mapping.

The key constraints are:

• Each record is unique for a (product, store) pair.
• You should not include products in a store's mapping if that store does not sell them.
• The output should be a dictionary (or mapping) where each key is a store, and the value is another dictionary mapping products to their prices at that store.

Thought Process

The first step is to consider how to organize the data so that it is easy to look up the price of any product at any store. A brute-force approach would be to iterate through the list for every store and every product, but this would be inefficient and repetitive.

A more efficient approach is to group the data by store first, and within each store, map each product to its price. This way, we avoid unnecessary checks and make lookups fast and direct. Using a dictionary (hash map) for both stores and products is ideal because it allows for quick insertion and retrieval.

The main idea is to build a nested dictionary: the outer dictionary's keys are store names, and each value is another dictionary mapping product names to their prices at that store.

Solution Approach

Let's break down the algorithm step by step:

1. Initialize an empty dictionary: This will hold the mapping from stores to their products and prices.
2. Iterate through each record: For each record in the input list, extract the store, product, and price.
3. Check if the store exists in the dictionary: If not, create a new dictionary for that store.
4. Add the product and price to the store's dictionary: Assign the product as a key and the price as its value.
5. Repeat until all records are processed.
6. Return the completed dictionary.

We use dictionaries because they provide O(1) time complexity for insertion and lookup, making the process efficient even for large datasets.

Example Walkthrough

Suppose the input is:

• {"product": "apple", "store": "StoreA", "price": 1}
• {"product": "banana", "store": "StoreA", "price": 2}
• {"product": "apple", "store": "StoreB", "price": 3}
• {"product": "orange", "store": "StoreB", "price": 4}

Let's process each record:

• First record: StoreA does not exist yet, so create it. Add "apple": 1.
• Second record: StoreA exists, add "banana": 2 to its mapping.
• Third record: StoreB does not exist yet, so create it. Add "apple": 3.
• Fourth record: StoreB exists, add "orange": 4 to its mapping.

{
  "StoreA": {"apple": 1, "banana": 2},
  "StoreB": {"apple": 3, "orange": 4}
}
    

Time and Space Complexity

Brute-force approach:

• Time Complexity: O(S * P), where S is the number of stores and P is the number of products. This is because for every store, you might scan the entire list for each product.
• Space Complexity: O(S * P), since you need to store the mapping for each store-product pair.

• Time Complexity: O(N), where N is the number of records. Each record is processed exactly once.
• Space Complexity: O(S * P), since you still store each store-product pair, but do not create unnecessary entries.

The optimized approach is much faster because it processes each record only once and uses hash maps for constant-time access.

Summary

In summary, the problem is elegantly solved by using a nested dictionary structure: the outer dictionary maps stores to their products, and the inner dictionary maps products to their prices. This approach is both efficient and easy to implement, avoiding unnecessary computations and making lookups fast. The key insight is to group data by store first, then by product, leveraging the power of hash maps for organization and efficiency.

Code Implementation

def products_price_for_each_store(records):
    result = {}
    for record in records:
        store = record['store']
        product = record['product']
        price = record['price']
        if store not in result:
            result[store] = {}
        result[store][product] = price
    return result
      

#include <unordered_map>
#include <string>
#include <vector>

using namespace std;

struct Record {
    string product;
    string store;
    int price;
};

unordered_map<string, unordered_map<string, int>> productsPriceForEachStore(const vector<Record>& records) {
    unordered_map<string, unordered_map<string, int>> result;
    for (const auto& record : records) {
        result[record.store][record.product] = record.price;
    }
    return result;
}
      

import java.util.*;

class Record {
    String product;
    String store;
    int price;
    Record(String product, String store, int price) {
        this.product = product;
        this.store = store;
        this.price = price;
    }
}

public class Solution {
    public Map<String, Map<String, Integer>> productsPriceForEachStore(List<Record> records) {
        Map<String, Map<String, Integer>> result = new HashMap<>();
        for (Record record : records) {
            result.computeIfAbsent(record.store, k -> new HashMap<>()).put(record.product, record.price);
        }
        return result;
    }
}
      

function productsPriceForEachStore(records) {
    const result = {};
    for (const record of records) {
        const { store, product, price } = record;
        if (!(store in result)) {
            result[store] = {};
        }
        result[store][product] = price;
    }
    return result;
}