Customers Who Bought All Products - Solution & Explanation
Problem Statement
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.
Approach Overview
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 1: Approach using SQL with Group By
In this approach, we'll use SQL's GROUP BY and HAVING clause to find customers who bought all products. We will count the number of distinct product_keys for each customer_id and compare it to the total number of products.
This SQL query groups rows by customer_id in the Customer table, then counts distinct product_key values for each group. The HAVING clause checks if the count for each customer_id equals the total count of products. Only customer_ids that satisfy this condition appear in the results.
Complexity
Time Complexity: O(N * M), where N is the number of customers and M is the number of products due to the join and counting.
Space Complexity: O(K), where K is the number of distinct customer_ids in the result.
Approach 2: Approach Using Programming Language with Hashmap/Dictionary
In this approach, we'll manually replicate the SQL logic using hash maps or dictionaries in a programming language. We'll count the distinct products each customer has bought using a hashmap and verify if it matches the total number of products.
We use a defaultdict to track products bought by each customer, forming a set for each customer to store unique products. After forming these sets, we iterate over to check whose product count equals product_count, the total number of products. Those customer_ids are captured and returned.
Code
Python
JavaScript
Java
C#
C++
Complexity
Time Complexity: O(N), processes each entry of customer_data.
Space Complexity: O(U), U being the summed size of sets in the dictionary.
Approach 3: Grouping and Subquery
We can group the Customer table by customer_id, and then use the HAVING clause to filter out the customers who have not purchased all products. To do this, we can use a subquery to find the total number of distinct products, and then compare it with the number of distinct products purchased by each customer.
Code
MySQL
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach using SQL with Group By | Time Complexity: O(N * M), where N is the number of customers and M is the number of products due to the join and counting. |
| Approach Using Programming Language with Hashmap/Dictionary | Time Complexity: O(N), processes each entry of customer_data. |
| Grouping and Subquery | — |
Detailed Complexity Analysis
| 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 |
Video Solution
Customers Who Bought All Products | Leetcode 1045 | Crack SQL Interviews in 50 Qs #mysql #leetcode • Learn With Chirag • 9,601 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Customers Who Bought All Products easy or hard?
Customers Who Bought All Products Python/Java solution
How to solve Customers Who Bought All Products in O(n)?
What is the best approach for Customers Who Bought All Products?
Is Customers Who Bought All Products asked at Google/Amazon/Meta?
What data structure is used in Customers Who Bought All Products?
What is the time complexity of Customers Who Bought All Products?
Ready to solve this problem?
Practice Customers Who Bought All Products with our built-in code editor and test cases.
Practice on FleetCode