Problem Breakdown
We are tasked with identifying customer_ids from the transaction log (Orders) that have purchased every single unique item available in the catalog (Product).
Inputs & Schema Assumptions: Based on standard LeetCode 1045 conventions, we assume access to:
Product: Containsproduct_key(unique identifier for each item). Note: There is typically no separateCustomerstable provided by default; customer IDs are derived from theOrderstable.Orders: Tracks purchases with columns(customer_id, product_key).
Outputs:
A list of unique customer_ids who have purchased all products. If no such customers exist (or if they haven’t bought anything), return an empty set or nulls depending on DB engine behavior for the query result.
Constraints & Edge Cases:
- Duplicate Purchases: A customer might buy the same item multiple times. We must count distinct product keys per customer (
COUNT(DISTINCT ...)). - Empty Product Catalog: If
Producttable is empty, total products = 0. Any customer with distinct purchase count of 0 (no orders) would technically satisfy “bought all” vacuously. However, usually we assume a populated product list or filter for customers who actually exist in the system contextually. - Missing Orders: A
customer_idonly appears if they have an order. If no customer has bought anything and products > 0, result is empty set.
Intuition
A brute-force approach would iterate through every possible combination of customers and products to check existence row-by-row (), which is inefficient for large datasets.
Key Insight: Instead of checking existence per item, we use aggregation:
- Calculate the total number of unique products available in
Product(Global Count). - For each customer found in
Orders, calculate how many distinct products they have purchased (Local Count). - Filter customers where
Local Count == Global Count.
This transforms a complex existence check into a simple arithmetic comparison using SQL aggregation (GROUP BY, HAVING).
Approach
- Calculate Total Products: Use a subquery
(SELECT COUNT(*) FROM Product)to get the total number of distinct products available in the system. Sinceproduct_keyis usually unique, this counts all rows/products. - Aggregate Customer Purchases: Group by
customer_idfrom theOrderstable and calculate the count of distinct product keys purchased per customer (COUNT(DISTINCT product_key)). Note: We select directly fromOrders, not joining a non-existentCustomerstable, to ensure compatibility with standard LC 1045 schema. - Filter with HAVING: Use a
HAVINGclause to keep only groups where the distinct purchase count equals the total products calculated in step 1. - Return Result: Select and return the filtered list of customer IDs.
Complexity Analysis
- Time Complexity: , where is the number of rows in
Orders(scanned for aggregation) and is the number of products (subquery). The aggregation (GROUP BY) typically runs linear time relative to input size with hash-based indexing. Comparing against total count is constant or logarithmic depending on implementation details but negligible compared to scanning orders. - Space Complexity: , where is the number of distinct customers involved in transactions (for grouping). We store intermediate counts for each customer during aggregation.
Edge Cases Handled
- Schema Accuracy: Corrected from proposed solution which assumed a
Customerstable that does not exist in standard LC 1045 schema. The query now selects directly fromOrders. - Duplicate Products: Uses
COUNT(DISTINCT product_key)to ignore multiple purchases of the same item by one customer, ensuring accurate comparison against total unique products. - Empty Product List: If
Productcount is 0 and a customer has no orders (count=0), they match. This handles the vacuous truth case mathematically correctly for SQL logic. - Null Values: Standard SQL aggregation ignores NULLs in counting, but since keys are usually primary/unique identifiers, this is handled implicitly by
COUNT(DISTINCT ...).
Solution
def get_customers_who_bought_all_products():
"""
Returns a SQL query string that solves LeetCode 1045.
In an interview context, this demonstrates the logic to be executed in DB environment.
Assumed Schema (Standard LC 1045):
Product(product_key) -- Unique identifier for each item
Orders(customer_id, product_key) -- Transaction log
Note: This function returns the SQL query string for execution against a database engine.
"""
sql_query = """
SELECT
customer_id
FROM Orders o
GROUP BY customer_id
HAVING COUNT(DISTINCT o.product_key) = (SELECT COUNT(*) FROM Product);
"""
# In a real Python environment with DB access, we would execute:
# cursor.execute(sql_query)
return sql_query
# Example usage to demonstrate the solution logic in code context if needed for mock interview validation
if __name__ == "__main__":
print(get_customers_who_bought_all_products())