Most Common Course Pairs solution and explanation
2 more videos on this problem
Leetcode HARD 3764 - Window Functions in SQL - Most Common Course Pairs | Everyday Data ScienceEveryday Data Science · 10:09 · 638 views
Crack🫠 LeetCode Hard SQL Fast! |😅 3764: Most Common Course PairsVivek The Analyst · 9:12 · 48 views
LeetCode, Pandas, 3764. Most Common Course Pairs, HardДиванная аналитика · 38:29 · 2 views
The problem
Table: course_completions
+-------------------+---------+ | Column Name | Type | +-------------------+---------+ | user_id | int | | course_id | int | | course_name | varchar | | completion_date | date | | course_rating | int | +-------------------+---------+ (user_id, course_id) is the combination of columns with unique values for this table. Each row represents a completed course by a user with their rating (1-5 scale).
Write a solution to identify skill mastery pathways by analyzing course completion sequences among top-performing students:
- Consider only top-performing students (those who completed at least
5courses with an average rating of4or higher). - For each top performer, identify the sequence of courses they completed in chronological order.
- Find all consecutive course pairs (
Course A → Course B) taken by these students. - Return the pair frequency, identifying which course transitions are most common among high achievers.
Return the result table ordered by pair frequency in descending order and then by first course name and second course name in ascending order.
The result format is in the following example.
Example:
Input:
course_completions table:
+---------+-----------+------------------+-----------------+---------------+ | user_id | course_id | course_name | completion_date | course_rating | +---------+-----------+------------------+-----------------+---------------+ | 1 | 101 | Python Basics | 2024-01-05 | 5 | | 1 | 102 | SQL Fundamentals | 2024-02-10 | 4 | | 1 | 103 | JavaScript | 2024-03-15 | 5 | | 1 | 104 | React Basics | 2024-04-20 | 4 | | 1 | 105 | Node.js | 2024-05-25 | 5 | | 1 | 106 | Docker | 2024-06-30 | 4 | | 2 | 101 | Python Basics | 2024-01-08 | 4 | | 2 | 104 | React Basics | 2024-02-14 | 5 | | 2 | 105 | Node.js | 2024-03-20 | 4 | | 2 | 106 | Docker | 2024-04-25 | 5 | | 2 | 107 | AWS Fundamentals | 2024-05-30 | 4 | | 3 | 101 | Python Basics | 2024-01-10 | 3 | | 3 | 102 | SQL Fundamentals | 2024-02-12 | 3 | | 3 | 103 | JavaScript | 2024-03-18 | 3 | | 3 | 104 | React Basics | 2024-04-22 | 2 | | 3 | 105 | Node.js | 2024-05-28 | 3 | | 4 | 101 | Python Basics | 2024-01-12 | 5 | | 4 | 108 | Data Science | 2024-02-16 | 5 | | 4 | 109 | Machine Learning | 2024-03-22 | 5 | +---------+-----------+------------------+-----------------+---------------+
Output:
+------------------+------------------+------------------+ | first_course | second_course | transition_count | +------------------+------------------+------------------+ | Node.js | Docker | 2 | | React Basics | Node.js | 2 | | Docker | AWS Fundamentals | 1 | | JavaScript | React Basics | 1 | | Python Basics | React Basics | 1 | | Python Basics | SQL Fundamentals | 1 | | SQL Fundamentals | JavaScript | 1 | +------------------+------------------+------------------+
Explanation:
- User 1: Completed 6 courses with average rating 4.5 (qualifies as top performer)
- User 2: Completed 5 courses with average rating 4.4 (qualifies as top performer)
- User 3: Completed 5 courses but average rating is 2.8 (does not qualify)
- User 4: Completed only 3 courses (does not qualify)
- Course Pairs Among Top Performers:
- User 1: Python Basics → SQL Fundamentals → JavaScript → React Basics → Node.js → Docker
- User 2: Python Basics → React Basics → Node.js → Docker → AWS Fundamentals
- Most common transitions: Node.js → Docker (2 times), React Basics → Node.js (2 times)
Results are ordered by transition_count in descending order, then by first_course in ascending order, and then by second_course in ascending order.
Approach overview
Problem Overview: Each student has a set of enrolled courses. Count how often each unordered pair of courses appears together for the same student, then return the pairs with the highest counts. Each pair should be counted once, regardless of order.
Approach 1: Nested Loop Pair Counting (O(∑kᵢ²) time, O(P) space)
Group enrollments by student. For each student with k courses, use two nested loops to visit every pair of courses (i, j) where i < j. Normalize each pair so the smaller course ID comes first, then increment a counter in a hash map keyed by that pair. This is the most direct translation of the problem. It works in any language, and the logic is easy to verify. The cost comes from students with many courses, because a student with k courses produces k(k-1)/2 pairs. Use this approach to confirm your understanding before optimizing.
Approach 2: Grouping and Counting with Self-Join (O(∑kᵢ²) time, O(P) space)
In SQL, self-join the enrollment table on student_id and keep rows where the left course_id is less than the right one. This generates every unordered pair per student in a single relational step. Then GROUP BY the two course columns, apply COUNT(*), and sort by the count in descending order. The database engine handles the pair generation and aggregation, so you write a declarative query instead of managing loops. In Pandas, the same idea works with a merge on student_id, a filter on the course columns, and groupby(...).size(). Prefer this approach when the data lives in a database or when you need a clean set-based solution.
Why the enumeration cost is unavoidable: Every co-occurring pair must be counted, so the output size P sets a lower bound on the work. The optimization is in avoiding duplicate pairs (the i < j filter halves the work) and in pushing aggregation into an indexed hash or sort step. You cannot skip students or pairs without changing the answer.
Recommended for interviews: Interviewers expect the grouping and counting approach. Write the brute force first to show you understand the pair definition, then move to the self-join with GROUP BY to show you can express the aggregation cleanly. Mention ordering and tie handling explicitly, since those details often decide the final answer. For more practice on this pattern, see database problems, hash table problems, and sorting problems.
Solution
Thinking
Course paths count consecutive completions of top students only. We first keep students with at least five courses and average rating at least
4, then emit adjacent pairs from each such student's time-ordered list, and finally aggregate and sort those pairs.
We first filter out all top students, denoted as top_students, i.e., students who have completed at least 5 courses with an average rating of at least 4. Then for each top student, we sort by completion time and find all consecutive course pairs, denoted as course_pairs. Finally, we group and count all course pairs, calculate the occurrence count of each course pair, and output the results sorted as required.
# Write your MySQL query statement below
WITH
top_students AS (
SELECT user_id
FROM course_completions
GROUP BY user_id
HAVING COUNT(1) >= 5 AND AVG(course_rating) >= 4
),
course_pairs AS (
SELECT
course_name AS first_course,
LEAD(course_name) OVER (
PARTITION BY user_id
ORDER BY completion_date
) second_course
FROM
top_students
JOIN course_completions USING (user_id)
)
SELECT
*,
COUNT(1) transition_count
FROM course_pairs
WHERE second_course IS NOT NULL
GROUP BY 1, 2
ORDER BY 3 DESC, 1, 2;import pandas as pd
def topLearnerCourseTransitions(course_completions: pd.DataFrame) -> pd.DataFrame:
grp = course_completions.groupby("user_id")
top_students = grp.filter(
lambda df: df.shape[0] >= 5 and df["course_rating"].mean() >= 4
)["user_id"].unique()
df = course_completions[course_completions["user_id"].isin(top_students)].copy()
df = df.sort_values(["user_id", "completion_date"])
df["second_course"] = df.groupby("user_id")["course_name"].shift(-1)
df["first_course"] = df["course_name"]
pairs = df[df["second_course"].notna()][["first_course", "second_course"]]
result = (
pairs.groupby(["first_course", "second_course"])
.size()
.reset_index(name="transition_count")
.sort_values(
["transition_count", "first_course", "second_course"],
ascending=[False, True, True],
key=lambda col: col.str.lower() if col.dtype == "object" else col,
)
.reset_index(drop=True)
)
return resultComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Nested Loop Pair Counting | O(∑kᵢ²) | O(P) | Learning the pair logic, small datasets, in-memory processing |
| Grouping and Counting (Self-Join) | O(∑kᵢ²) | O(P) | Data in a database, set-based queries, interview and production SQL |
Frequently asked questions
Is Most Common Course Pairs easy or hard?
It is rated hard, but the core idea is simple once you see it. The difficulty comes from correctly defining unordered pairs, avoiding duplicate counts, and handling ties and ordering in the output. Practice the self-join pattern and the pair normalization step to make it routine.
Most Common Course Pairs Python solution?
Group the enrollments by student, then for each student use itertools.combinations on the sorted list of courses. Increment a Counter keyed by each pair. Finally, sort the counter by count in descending order and return the top results. In Pandas, you can use merge on student_id, filter the course pairs, and call groupby with size.
How to solve Most Common Course Pairs in O(n)?
A true O(n) solution is not possible because every co-occurring pair has to be counted, and a student with many courses generates many pairs. The practical optimization is to generate only unordered pairs (i < j) and aggregate with a hash map or GROUP BY. This keeps the work proportional to the number of pairs, not the square of all course IDs.
What is the best approach for Most Common Course Pairs?
The best approach is grouping and counting. Self-join the enrollments on student_id, keep only pairs where the first course ID is less than the second, then GROUP BY the pair and COUNT the rows. Sort by the count in descending order to get the most common pairs.
What data structure is used in Most Common Course Pairs?
The main data structure is a hash map or grouped aggregation that maps each course pair to its count. In SQL, this is handled by GROUP BY with COUNT(*). In Python, a dictionary keyed by a tuple of two course IDs works well.
What is the time complexity of Most Common Course Pairs?
The time complexity is O(∑kᵢ²), where kᵢ is the number of courses taken by student i. Each student contributes k(k-1)/2 pairs, and the aggregation step is hash-based or sort-based on the total number of pairs P. The space complexity is O(P) for the pair counts.
Is Most Common Course Pairs asked at Google, Amazon, or Meta?
Most Common Course Pairs is a database-style problem, and it is commonly practiced for SQL interviews at large tech companies such as Google, Amazon, and Meta. Check the company-specific question lists on FleetCode for the latest reported frequency, since these lists change over time.