Find Category Recommendation Pairs solution and explanation
5 more videos on this problem
Leetcode HARD 3554 - Self Joins AMAZON - Find Category Recommendation Pairs | Everyday Data ScienceEveryday Data Science · 11:55 · 605 views
Leetcode: 3554 Find Category Recommendation PairsInsightVanta · 9:23 · 142 views
LeetCode, SQL, 3554. Find Category Recommendation Pairs, HardДиванная аналитика · 34:17 · 7 views
Find Category Recommendation PairsOwen Wu · 8:29 · 4 views
LeetCode, Pandas, 3554. Find Category Recommendation Pairs, HardДиванная аналитика · 18:26 · 4 views
😨Crack this HARD Amazon SQL Problem! 🛒 (Category Recommendation Pairs)👍🏻Vivek The Analyst · 9:45 · 23 views
The problem
Table: ProductPurchases
+-------------+------+ | Column Name | Type | +-------------+------+ | user_id | int | | product_id | int | | quantity | int | +-------------+------+ (user_id, product_id) is the unique identifier 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 unique identifier for this table. Each row assigns a category and price to a product.
Amazon wants to understand shopping patterns across product categories. Write a solution to:
- Find all category pairs (where
category1<category2) - For each category pair, determine the number of unique customers who purchased products from both categories
A category pair is considered reportable if at least 3 different customers have purchased products from both categories.
Return the result table of reportable category pairs ordered by customer_count in descending order, and in case of a tie, by category1 in ascending order lexicographically, and then by category2 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 | 201 | 3 | | 1 | 301 | 1 | | 2 | 101 | 1 | | 2 | 102 | 2 | | 2 | 103 | 1 | | 2 | 201 | 5 | | 3 | 101 | 2 | | 3 | 103 | 1 | | 3 | 301 | 4 | | 3 | 401 | 2 | | 4 | 101 | 1 | | 4 | 201 | 3 | | 4 | 301 | 1 | | 4 | 401 | 2 | | 5 | 102 | 2 | | 5 | 103 | 1 | | 5 | 201 | 2 | | 5 | 202 | 3 | +---------+------------+----------+
ProductInfo table:
+------------+-------------+-------+ | product_id | category | price | +------------+-------------+-------+ | 101 | Electronics | 100 | | 102 | Books | 20 | | 103 | Books | 35 | | 201 | Clothing | 45 | | 202 | Clothing | 60 | | 301 | Sports | 75 | | 401 | Kitchen | 50 | +------------+-------------+-------+
Output:
+-------------+-------------+----------------+ | category1 | category2 | customer_count | +-------------+-------------+----------------+ | Books | Clothing | 3 | | Books | Electronics | 3 | | Clothing | Electronics | 3 | | Electronics | Sports | 3 | +-------------+-------------+----------------+
Explanation:
- Books-Clothing:
- User 1 purchased products from Books (102) and Clothing (201)
- User 2 purchased products from Books (102, 103) and Clothing (201)
- User 5 purchased products from Books (102, 103) and Clothing (201, 202)
- Total: 3 customers purchased from both categories
- Books-Electronics:
- User 1 purchased products from Books (102) and Electronics (101)
- User 2 purchased products from Books (102, 103) and Electronics (101)
- User 3 purchased products from Books (103) and Electronics (101)
- Total: 3 customers purchased from both categories
- Clothing-Electronics:
- User 1 purchased products from Clothing (201) and Electronics (101)
- User 2 purchased products from Clothing (201) and Electronics (101)
- User 4 purchased products from Clothing (201) and Electronics (101)
- Total: 3 customers purchased from both categories
- Electronics-Sports:
- User 1 purchased products from Electronics (101) and Sports (301)
- User 3 purchased products from Electronics (101) and Sports (301)
- User 4 purchased products from Electronics (101) and Sports (301)
- Total: 3 customers purchased from both categories
- Other category pairs like Clothing-Sports (only 2 customers: Users 1 and 4) and Books-Kitchen (only 1 customer: User 3) have fewer than 3 shared customers and are not included in the result.
The result is ordered by customer_count in descending order. Since all pairs have the same customer_count of 3, they are ordered by category1 (then category2) in ascending order.
Approach overview
Problem Overview: You get purchase records (user_id, product_id, quantity) and a product-to-category mapping. Return every category pair (category1, category2) with category1 less than category2 where at least 3 distinct customers bought from both categories. Sort by customer count descending, then by category names ascending.
Approach 1: Correlated Subquery per Category Pair (O(C² × N) time, O(1) extra space)
Build the list of all distinct categories and test each pair directly. For each pair, run a correlated subquery that counts users who appear in purchases of both categories. This works because it checks the definition literally, with no intermediate tables. The cost grows fast: with C categories you evaluate about C²/2 pairs, and each check scans the purchase data again. Use it only to confirm your understanding of the condition.
Approach 2: Distinct User-Category Self-Join with Group Aggregation (O(U × k² ) time, O(U × k) space)
First, join ProductPurchases to ProductInfo so every row carries a category. Then reduce that to distinct (user_id, category) pairs. A user who bought five products from one category should count once for that category. Self-join the distinct set on user_id, keep only rows where the left category is less than the right category, and group by the category pair. Apply COUNT(DISTINCT user_id) and HAVING COUNT(DISTINCT user_id) >= 3. The c1.category < c2.category filter removes mirrored duplicates like (A, B) and (B, A), which halves the work and keeps the output canonical. Here, k is the number of distinct categories per user, which is usually small, so the self-join stays cheap.
Approach 3: Pre-Aggregated CTE with Join (Optimal for Large Logs)
Put the DISTINCT step in a CTE named user_categories, then join that CTE to itself. Hash-based joins in MySQL 8 and most warehouse engines handle this shape well. Time stays O(U × k²) in the worst case, and space is O(U × k) for the materialized CTE. This is the version you should write in an interview. It separates the dedupe logic from the pair logic, which makes it easy to explain and debug.
Recommended for interviews: Interviewers expect the self-join with a distinct user-category step (Approach 2 or 3). The correlated subquery shows you understand the requirement, but the join-and-aggregate pattern shows you can reason about duplicates, canonical pair ordering, and aggregation. Mention the category1 < category2 filter early, since it is the detail most candidates miss. For more practice on this pattern, see database problems, join techniques, and aggregation.
Solution
Thinking
A recommendation pair is two distinct categories bought together by at least three users. Join purchases to product info, then drop duplicate
(user_id,category)rows.Self-join categories of the same user into ordered pairs, count distinct users, keep counts
\ge 3, and sort by count then names.
First, we join the ProductPurchases table and the ProductInfo table on product_id to obtain a user_category table consisting of user_id and category. Next, we self-join the user_category table to get all category pairs purchased by each user. Finally, we group these category pairs, count the number of users for each pair, and filter out the pairs with at least 3 users.
Lastly, we sort the final result by customer count in descending order, then by category1 in ascending order, and then by category2 in ascending order.
# Write your MySQL query statement below
WITH
user_category AS (
SELECT DISTINCT
user_id,
category
FROM
ProductPurchases
JOIN ProductInfo USING (product_id)
),
pair_per_user AS (
SELECT
a.user_id,
a.category AS category1,
b.category AS category2
FROM
user_category AS a
JOIN user_category AS b ON a.user_id = b.user_id AND a.category < b.category
)
SELECT category1, category2, COUNT(DISTINCT user_id) AS customer_count
FROM pair_per_user
GROUP BY 1, 2
HAVING customer_count >= 3
ORDER BY 3 DESC, 1, 2;import pandas as pd
def find_category_recommendation_pairs(
product_purchases: pd.DataFrame, product_info: pd.DataFrame
) -> pd.DataFrame:
df = product_purchases[["user_id", "product_id"]].merge(
product_info[["product_id", "category"]], on="product_id", how="inner"
)
user_category = df.drop_duplicates(subset=["user_id", "category"])
pair_per_user = (
user_category.merge(user_category, on="user_id")
.query("category_x < category_y")
.rename(columns={"category_x": "category1", "category_y": "category2"})
)
pair_counts = (
pair_per_user.groupby(["category1", "category2"])["user_id"]
.nunique()
.reset_index(name="customer_count")
)
result = (
pair_counts.query("customer_count >= 3")
.sort_values(
["customer_count", "category1", "category2"], ascending=[False, True, True]
)
.reset_index(drop=True)
)
return resultComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Correlated Subquery per Pair | O(C² × N) | O(1) extra | Checking the definition on small data |
| Distinct User-Category Self-Join | O(U × k²) | O(U × k) | General case, interview answer |
| Pre-Aggregated CTE with Join | O(U × k²) | O(U × k) | Large logs, reusable intermediate result |
Frequently asked questions
Is Find Category Recommendation Pairs easy or hard?
It is rated Hard, even though the final SQL is short. The difficulty comes from three details: deduplicating user-category pairs so repeat purchases do not inflate counts, avoiding mirrored pairs, and applying the distinct-customer threshold correctly in HAVING.
Find Category Recommendation Pairs Python/Java solution
This problem is written as a SQL query, so the main solution is MySQL. On FleetCode, the same join-and-aggregate logic is available in Pandas. Merge the purchases with product categories, drop duplicate user-category pairs, self-merge on user_id, filter category1 < category2, then group and count distinct users with at least 3.
How to solve Find Category Recommendation Pairs in O(n)?
A strict O(n) solution is not possible for this problem because you must compare categories that share a user, which is a pairwise operation. Reduce the input first with DISTINCT on (user_id, category), then self-join that smaller set. The work scales with the number of user-category pairs, not with the raw purchase count.
What is the best approach for Find Category Recommendation Pairs?
The best approach is a self-join on distinct (user_id, category) pairs, followed by GROUP BY on the category pair and a HAVING clause that requires at least 3 distinct users. Filter with category1 < category2 so each pair appears once. This runs in O(U × k²) time, where k is the number of categories per user.
Is Find Category Recommendation Pairs asked at Google/Amazon/Meta?
This problem is a SQL database question on LeetCode and is not publicly tagged to a specific company in our data. It is most useful for practicing self-joins and GROUP BY with HAVING, which appear often in data-focused interviews at companies like Amazon, Meta, and Google.
What data structure is used in Find Category Recommendation Pairs?
The problem uses relational tables, specifically ProductPurchases and ProductInfo. The solution relies on a derived table or CTE of distinct user-category pairs and a self-join on user_id. No hash map or array is needed in SQL, though the database engine may use a hash join internally.
What is the time complexity of Find Category Recommendation Pairs?
The optimal join-and-aggregate solution runs in O(U × k²) time, where U is the number of users and k is the average number of distinct categories per user. The naive approach that tests every category pair runs in O(C² × N) time, where C is the category count and N is the number of purchase rows.