Find Product Recommendation Pairs solution and explanation
5 more videos on this problem
Leetcode MEDIUM 3521 - SELF JOIN in SQL - Amazon Product Recommendation Pair | Everyday Data ScienceEveryday Data Science · 12:09 · 1K views
3521. Find Product Recommendation Pairs | LeetCode Solution ExplainedInsightVanta · 11:56 · 194 views
Master Self Joins Analytics|LeetCode 3521 Product Recommendation Pairs|Amazon SQL Interview QuestionVivek The Analyst · 10:55 · 51 views
SQL vs Pandas | Ace the Co-Purchase Pattern Interview Question | Leetcode 3521DataHead Girl · 8:33 · 26 views
LeetCode, Pandas, 3521. Find Product Recommendation Pairs уровень MEDIUMДиванная аналитика · 40:18 · 2 views
LeetCode, SQL, 3521. Find Product Recommendation Pairs уровень MEDIUMДиванная аналитика · 20:49 · 1 view
The problem
Table: ProductPurchases
+-------------+------+ | Column Name | Type | +-------------+------+ | user_id | int | | product_id | int | | quantity | int | +-------------+------+ (user_id, product_id) is the unique key for this table. Each row represents a purchase of a product by a user in a specific quantity.
Table: ProductInfo
+-------------+---------+ | Column Name | Type | +-------------+---------+ | product_id | int | | category | varchar | | price | decimal | +-------------+---------+ product_id is the primary key for this table. Each row assigns a category and price to a product.
Amazon wants to implement the Customers who bought this also bought... feature based on co-purchase patterns. Write a solution to :
- Identify distinct product pairs frequently purchased together by the same customers (where
product1_id<product2_id) - For each product pair, determine how many customers purchased both products
A product pair is considered for recommendation if at least 3 different customers have purchased both products.
Return the result table ordered by customer_count in descending order, and in case of a tie, by product1_id in ascending order, and then by product2_id in ascending order.
The result format is in the following example.
Example:
Input:
ProductPurchases table:
+---------+------------+----------+ | user_id | product_id | quantity | +---------+------------+----------+ | 1 | 101 | 2 | | 1 | 102 | 1 | | 1 | 103 | 3 | | 2 | 101 | 1 | | 2 | 102 | 5 | | 2 | 104 | 1 | | 3 | 101 | 2 | | 3 | 103 | 1 | | 3 | 105 | 4 | | 4 | 101 | 1 | | 4 | 102 | 1 | | 4 | 103 | 2 | | 4 | 104 | 3 | | 5 | 102 | 2 | | 5 | 104 | 1 | +---------+------------+----------+
ProductInfo table:
+------------+-------------+-------+ | product_id | category | price | +------------+-------------+-------+ | 101 | Electronics | 100 | | 102 | Books | 20 | | 103 | Clothing | 35 | | 104 | Kitchen | 50 | | 105 | Sports | 75 | +------------+-------------+-------+
Output:
+-------------+-------------+-------------------+-------------------+----------------+ | product1_id | product2_id | product1_category | product2_category | customer_count | +-------------+-------------+-------------------+-------------------+----------------+ | 101 | 102 | Electronics | Books | 3 | | 101 | 103 | Electronics | Clothing | 3 | | 102 | 104 | Books | Kitchen | 3 | +-------------+-------------+-------------------+-------------------+----------------+
Explanation:
- Product pair (101, 102):
- Purchased by users 1, 2, and 4 (3 customers)
- Product 101 is in Electronics category
- Product 102 is in Books category
- Product pair (101, 103):
- Purchased by users 1, 3, and 4 (3 customers)
- Product 101 is in Electronics category
- Product 103 is in Clothing category
- Product pair (102, 104):
- Purchased by users 2, 4, and 5 (3 customers)
- Product 102 is in Books category
- Product 104 is in Kitchen category
The result is ordered by customer_count in descending order. For pairs with the same customer_count, they are ordered by product1_id and then product2_id in ascending order.
Approach overview
Problem Overview: You have a table of customer purchases and a table of product metadata. Return every pair of distinct products that were bought together by at least 3 different customers, along with each product's category and the count of shared customers. Each pair should appear once, with the smaller product_id first.
Approach 1: Brute Force Per-Customer Pairing in Application Code (O(U * P^2) time, O(P^2) space)
Pull every purchase row into your application, group products by user_id, and generate all product pairs for each user. Increment a counter for each pair in a dictionary keyed by (product1, product2). At the end, filter pairs with a count of at least 3. This works, but it moves the heavy lifting out of the database and scales poorly when a single customer buys many products. Use it only to confirm your understanding of the logic.
Approach 2: SQL Self-Join with GROUP BY and HAVING (O(sum of k_u^2) time, O(output) space)
Join the purchases table to itself on user_id. Add the condition p1.product_id < p2.product_id so each unordered pair appears once and self-pairs are excluded. Group by the two product IDs and count distinct user_id values. Apply HAVING COUNT(DISTINCT user_id) >= 3 to keep only the frequent pairs. The key insight is that the join itself enumerates co-purchases per customer, and the distinct count prevents a customer who bought the same two products across several orders from being counted more than once. Join database concepts such as self-joins and aggregation here. Use this approach whenever the data lives in a relational database, which is the expected setting for this problem.
Approach 3: Pre-Deduplicated CTE with Self-Join (O(sum of k_u^2) time, O(U * P) space)
First collapse the purchases table to unique (user_id, product_id) rows in a CTE using SELECT DISTINCT or GROUP BY. Then run the same self-join against this smaller set. This removes duplicate rows caused by repeat orders before the expensive join runs, which makes the logic easier to reason about and avoids needing COUNT(DISTINCT) in the aggregation. Use it when the source table has many repeat purchases per customer and you want the join to operate on a clean set. The extra CTE adds a materialization step, so on very large tables with good indexes, Approach 2 is usually just as fast.
Recommended for interviews: Interviewers expect Approach 2. The application-code brute force shows you understand the pairing logic, but the self-join with a distinct count shows you can express it set-wise in SQL and handle duplicate purchases correctly. Mention the p1.product_id < p2.product_id guard and the COUNT(DISTINCT user_id) without being asked. Those two details separate a correct answer from a wrong one. For more practice on set-based problems, see SQL and aggregation.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Application-code pairing | O(U * P^2) | O(P^2) | Debugging logic, no SQL access |
| Self-join with GROUP BY and HAVING | O(sum of k_u^2) | O(output pairs) | General case, expected in interviews |
| Pre-deduplicated CTE with self-join | O(sum of k_u^2) | O(U * P) | Many repeat purchases per customer |
Frequently asked questions
Is Find Product Recommendation Pairs easy or hard?
It is rated Medium with an acceptance rate of about 63.4%. The logic is straightforward once you see the self-join pattern. The common mistakes are forgetting the product ordering condition, which double-counts pairs, and using COUNT instead of COUNT(DISTINCT user_id), which overcounts repeat purchases.
How to solve Find Product Recommendation Pairs in O(n)?
A true O(n) solution is not possible because every co-purchase pair must be enumerated at least once. The practical goal is to minimize work per customer. Deduplicate (user_id, product_id) first, then self-join with an ordering condition on product IDs so each pair is counted once.
Find Product Recommendation Pairs Python or Java solution?
Since the problem is a SQL question, the solution is a query rather than Python or Java code. If you need an application-level version, group purchases by user into sets, generate sorted product pairs per user, and count them in a dictionary. Keep only pairs with a count of at least 3.
What is the best approach for Find Product Recommendation Pairs?
The best approach is a SQL self-join on the purchases table using user_id, with p1.product_id < p2.product_id to avoid duplicate and self pairs. Group by the two product IDs, count DISTINCT user_id, and filter with HAVING COUNT(DISTINCT user_id) >= 3. Join the result to product info to add categories.
What data structure is used in Find Product Recommendation Pairs?
There is no classic data structure involved because the problem is written in SQL. The core tools are a self-join on the purchases table, GROUP BY for aggregation, and COUNT(DISTINCT user_id) to count unique customers per product pair. In application code, a hash map keyed by product pairs is the equivalent.
What is the time complexity of Find Product Recommendation Pairs?
The self-join approach runs in roughly O(sum of k_u^2) time, where k_u is the number of distinct products bought by user u. Space depends on the number of qualifying pairs in the output. Exact performance also depends on indexes on user_id and product_id in your database engine.
Is Find Product Recommendation Pairs asked at Google, Amazon, or Meta?
This problem is a Medium SQL question from LeetCode's Database topic. Co-purchase and recommendation queries are common in e-commerce interviews, so companies with large retail or marketplace products, such as Amazon, are the most likely to ask similar questions. Confirm current company-specific reports on LeetCode before preparing around them.