LeetCode #3521 — MEDIUM

Find Product Recommendation Pairs

Move from brute-force thinking to an efficient approach using core interview patterns strategy.

The Problem

Problem Statement

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.

Step 01

Brute Force Baseline

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: General problem-solving

Example 1

{"headers":{"ProductPurchases":["user_id","product_id","quantity"],"ProductInfo":["product_id","category","price"]},"rows":{"ProductPurchases":[[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":[[101,"Electronics",100],[102,"Books",20],[103,"Clothing",35],[104,"Kitchen",50],[105,"Sports",75]]}}

Step 02

Core Insight

What unlocks the optimal approach

No official hints in dataset. Start from constraints and look for a monotonic or reusable state.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Upper-end input sizes

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3521: Find Product Recommendation Pairs
// Auto-generated Java example from rust.
class Solution {
    public void exampleSolution() {
    }
}
// Reference (rust):
// // Accepted solution for LeetCode #3521: Find Product Recommendation Pairs
// pub fn sql_example() -> &'static str {
//     r#"
// -- Accepted solution for LeetCode #3521: Find Product Recommendation Pairs
// SELECT
//   P1.product_id AS product1_id,
//   P2.product_id AS product2_id,
//   PI1.category AS product1_category,
//   PI2.category AS product2_category,
//   COUNT(P1.user_id) AS customer_count
// FROM ProductPurchases AS P1
// INNER JOIN ProductPurchases AS P2
//   USING (user_id)
// LEFT JOIN ProductInfo AS PI1
//   ON (P1.product_id = PI1.product_id)
// LEFT JOIN ProductInfo AS PI2
//   ON (P2.product_id = PI2.product_id)
// WHERE P1.product_id < P2.product_id
// GROUP BY 1, 2, 3, 4
// HAVING COUNT(P1.user_id) >= 3
// ORDER BY customer_count DESC, product1_id, product2_id;
// "#
// }

// Accepted solution for LeetCode #3521: Find Product Recommendation Pairs
// Auto-generated Go example from rust.
func exampleSolution() {
}
// Reference (rust):
// // Accepted solution for LeetCode #3521: Find Product Recommendation Pairs
// pub fn sql_example() -> &'static str {
//     r#"
// -- Accepted solution for LeetCode #3521: Find Product Recommendation Pairs
// SELECT
//   P1.product_id AS product1_id,
//   P2.product_id AS product2_id,
//   PI1.category AS product1_category,
//   PI2.category AS product2_category,
//   COUNT(P1.user_id) AS customer_count
// FROM ProductPurchases AS P1
// INNER JOIN ProductPurchases AS P2
//   USING (user_id)
// LEFT JOIN ProductInfo AS PI1
//   ON (P1.product_id = PI1.product_id)
// LEFT JOIN ProductInfo AS PI2
//   ON (P2.product_id = PI2.product_id)
// WHERE P1.product_id < P2.product_id
// GROUP BY 1, 2, 3, 4
// HAVING COUNT(P1.user_id) >= 3
// ORDER BY customer_count DESC, product1_id, product2_id;
// "#
// }

# Accepted solution for LeetCode #3521: Find Product Recommendation Pairs
# Auto-generated Python example from rust.
def example_solution() -> None:
    return
# Reference (rust):
# // Accepted solution for LeetCode #3521: Find Product Recommendation Pairs
# pub fn sql_example() -> &'static str {
#     r#"
# -- Accepted solution for LeetCode #3521: Find Product Recommendation Pairs
# SELECT
#   P1.product_id AS product1_id,
#   P2.product_id AS product2_id,
#   PI1.category AS product1_category,
#   PI2.category AS product2_category,
#   COUNT(P1.user_id) AS customer_count
# FROM ProductPurchases AS P1
# INNER JOIN ProductPurchases AS P2
#   USING (user_id)
# LEFT JOIN ProductInfo AS PI1
#   ON (P1.product_id = PI1.product_id)
# LEFT JOIN ProductInfo AS PI2
#   ON (P2.product_id = PI2.product_id)
# WHERE P1.product_id < P2.product_id
# GROUP BY 1, 2, 3, 4
# HAVING COUNT(P1.user_id) >= 3
# ORDER BY customer_count DESC, product1_id, product2_id;
# "#
# }

// Accepted solution for LeetCode #3521: Find Product Recommendation Pairs
pub fn sql_example() -> &'static str {
    r#"
-- Accepted solution for LeetCode #3521: Find Product Recommendation Pairs
SELECT
  P1.product_id AS product1_id,
  P2.product_id AS product2_id,
  PI1.category AS product1_category,
  PI2.category AS product2_category,
  COUNT(P1.user_id) AS customer_count
FROM ProductPurchases AS P1
INNER JOIN ProductPurchases AS P2
  USING (user_id)
LEFT JOIN ProductInfo AS PI1
  ON (P1.product_id = PI1.product_id)
LEFT JOIN ProductInfo AS PI2
  ON (P2.product_id = PI2.product_id)
WHERE P1.product_id < P2.product_id
GROUP BY 1, 2, 3, 4
HAVING COUNT(P1.user_id) >= 3
ORDER BY customer_count DESC, product1_id, product2_id;
"#
}

// Accepted solution for LeetCode #3521: Find Product Recommendation Pairs
// Auto-generated TypeScript example from rust.
function exampleSolution(): void {
}
// Reference (rust):
// // Accepted solution for LeetCode #3521: Find Product Recommendation Pairs
// pub fn sql_example() -> &'static str {
//     r#"
// -- Accepted solution for LeetCode #3521: Find Product Recommendation Pairs
// SELECT
//   P1.product_id AS product1_id,
//   P2.product_id AS product2_id,
//   PI1.category AS product1_category,
//   PI2.category AS product2_category,
//   COUNT(P1.user_id) AS customer_count
// FROM ProductPurchases AS P1
// INNER JOIN ProductPurchases AS P2
//   USING (user_id)
// LEFT JOIN ProductInfo AS PI1
//   ON (P1.product_id = PI1.product_id)
// LEFT JOIN ProductInfo AS PI2
//   ON (P2.product_id = PI2.product_id)
// WHERE P1.product_id < P2.product_id
// GROUP BY 1, 2, 3, 4
// HAVING COUNT(P1.user_id) >= 3
// ORDER BY customer_count DESC, product1_id, product2_id;
// "#
// }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(n)

Space

O(1)

Approach Breakdown

BRUTE FORCE

O(n²) time

O(1) space

Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.

OPTIMIZED

O(n) time

O(1) space

Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.

Shortcut: If you are using nested loops on an array, there is almost always an O(n) solution. Look for the right auxiliary state.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.