Watch 10 video solutions for Customers Who Bought All Products, a medium level problem involving Database. This walkthrough by Learn With Chirag has 8,649 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Table: Customer
+-------------+---------+ | Column Name | Type | +-------------+---------+ | customer_id | int | | product_key | int | +-------------+---------+ This table may contain duplicates rows.customer_idis not NULL.product_key is a foreign key (reference column) toProducttable.
Table: Product
+-------------+---------+ | Column Name | Type | +-------------+---------+ | product_key | int | +-------------+---------+ product_key is the primary key (column with unique values) for this table.
Write a solution to report the customer ids from the Customer table that bought all the products in the Product table.
Return the result table in any order.
The result format is in the following example.
Example 1:
Input: Customer table: +-------------+-------------+ | customer_id | product_key | +-------------+-------------+ | 1 | 5 | | 2 | 6 | | 3 | 5 | | 3 | 6 | | 1 | 6 | +-------------+-------------+ Product table: +-------------+ | product_key | +-------------+ | 5 | | 6 | +-------------+ Output: +-------------+ | customer_id | +-------------+ | 1 | | 3 | +-------------+ Explanation: The customers who bought all the products (5 and 6) are customers with IDs 1 and 3.
Problem Overview: You are given a purchase table that records which customer bought which product. The goal is to return all customers who have purchased every product that exists in the Products table. A valid customer must have bought each product at least once.
Approach 1: SQL GROUP BY with COUNT(DISTINCT) (O(n log n) time, O(n) space)
This is the standard relational database solution. First determine the total number of products using COUNT(*) on the Product table. Then group the Customer purchase records by customer_id and count how many distinct products each customer bought. If that count matches the total number of products, the customer purchased the full catalog. SQL engines internally use grouping and sorting or hashing, which leads to roughly O(n log n) processing depending on indexing. This approach is concise, declarative, and preferred when solving problems tagged under Database or SQL.
Approach 2: HashMap / Dictionary Counting (O(n) time, O(n) space)
If you implement the logic in a programming language instead of pure SQL, track purchases using a hash map. First compute the number of unique products from the product list. Then iterate through the purchase records and store products bought by each customer inside a hash set or dictionary entry. After processing all records, check which customers have a product set size equal to the total product count. Hash lookups and insertions run in constant time, so the overall complexity is O(n) for n purchase rows. This approach mirrors typical interview-style reasoning using hash tables or dictionaries.
Key Insight: The problem reduces to comparing two counts: the total number of products in the system and the number of unique products purchased by each customer. As soon as those values match, the customer qualifies.
Recommended for interviews: Interviewers usually expect the counting insight first. Explaining the hash set or dictionary method demonstrates algorithmic thinking and clean O(n) reasoning. For database-focused interviews, the GROUP BY + HAVING COUNT(DISTINCT ...) solution is the canonical answer and shows strong SQL fundamentals.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| SQL GROUP BY + COUNT(DISTINCT) | O(n log n) | O(n) | Best for database queries or SQL interviews where aggregation is expected |
| HashMap / Dictionary with Sets | O(n) | O(n) | General programming solution when solving outside SQL using Python, Java, or JavaScript |
