Table: ActorDirector
+-------------+---------+ | Column Name | Type | +-------------+---------+ | actor_id | int | | director_id | int | | timestamp | int | +-------------+---------+ timestamp is the primary key (column with unique values) for this table.
Write a solution to find all the pairs (actor_id, director_id) where the actor has cooperated with the director at least three times.
Return the result table in any order.
The result format is in the following example.
Example 1:
Input: ActorDirector table: +-------------+-------------+-------------+ | actor_id | director_id | timestamp | +-------------+-------------+-------------+ | 1 | 1 | 0 | | 1 | 1 | 1 | | 1 | 1 | 2 | | 1 | 2 | 3 | | 1 | 2 | 4 | | 2 | 1 | 5 | | 2 | 1 | 6 | +-------------+-------------+-------------+ Output: +-------------+-------------+ | actor_id | director_id | +-------------+-------------+ | 1 | 1 | +-------------+-------------+ Explanation: The only pair is (1, 1) where they cooperated exactly 3 times.
Problem Overview: You are given a table that records collaborations between actors and directors. Each row contains an actor_id and a director_id. The task is to return all pairs that have worked together at least three times.
Approach 1: Using a HashMap to Count Occurrences (Time: O(n), Space: O(n))
Iterate through each row and treat the pair (actor_id, director_id) as a key. Store the count of collaborations in a hash map. Every time the same pair appears again, increment the stored value. After processing all rows, iterate through the map and collect pairs where the count is greater than or equal to three.
The key insight is that collaboration pairs repeat across rows. A hash map provides constant-time lookup and updates, which makes counting efficient. This approach works well if you are processing the dataset in application code (Python, Java, C++, etc.) instead of directly querying the database.
Approach 2: Using SQL GROUP BY and HAVING Clause (Time: O(n), Space: O(1) additional)
Group the rows by actor_id and director_id using the SQL GROUP BY clause. For each group, compute the number of rows using COUNT(*). Then filter the results with a HAVING COUNT(*) >= 3 condition to keep only pairs that collaborated at least three times.
This approach pushes the counting work to the database engine. Modern SQL engines optimize grouping and aggregation very efficiently. It is the most natural solution for database problems and avoids transferring unnecessary data into application memory.
Because the dataset is already stored in a relational table, grouping and aggregation through SQL is both concise and performant.
Recommended for interviews: The SQL GROUP BY with HAVING solution is what interviewers typically expect for database questions. It demonstrates understanding of aggregation and filtering directly in SQL. The hash map approach is still valuable when the data is processed in application code or when practicing algorithmic counting patterns.
This approach involves iterating through the given table and using a hash map (or dictionary) to count how many times each actor-director pair appears. After counting, you can filter these pairs to only include those that have a count of three or more.
This C solution uses a hash map implemented with an array of linked lists to count occurrences of actor-director pairs. The hash function determines the index in the array, where a linked list stores pairs. As we iterate through the input, if a pair already exists in the structure, its count is incremented. Finally, all pairs with counts of three or higher are outputted.
Time Complexity: O(n), where n is the number of entries in the table.
Space Complexity: O(m), where m is the number of distinct actor-director pairs.
If this were a SQL-based system, an efficient way to find the actors and directors who have cooperated at least three times is by using SQL's GROUP BY and HAVING clauses. The GROUP BY clause allows us to group rows that have the same values in specified columns, while the HAVING clause will filter these groups based on a given condition.
In this SQL solution, we group the entries in the ActorDirector table by actor_id and director_id. The HAVING clause ensures that only pairs with three or more entries in the table are selected for the final result.
SQL
Time Complexity: O(n log n), due to potential sorting in the GROUP BY operation.
Space Complexity: O(k), where k is the number of groups formed from distinct pairs of actors and directors.
We can use the GROUP BY statement to group the data by the actor_id and director_id fields, and then use the HAVING statement to filter out the actor_id and director_id that appear at least three times.
MySQL
| Approach | Complexity |
|---|---|
| Approach 1: Using a HashMap to Count Occurrences | Time Complexity: O(n), where n is the number of entries in the table. |
| Approach 2: Using SQL Group By and Having Clause | Time Complexity: O(n log n), due to potential sorting in the GROUP BY operation. |
| Group By + Having | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashMap Counting | O(n) | O(n) | When processing collaboration data in application code rather than directly in SQL |
| SQL GROUP BY + HAVING | O(n) | O(1) additional | Best for database queries where aggregation and filtering can be handled by the SQL engine |
LeetCode Interview SQL Question with Detailed Explanation | Practice SQL | LeetCode 1050 • Everyday Data Science • 14,168 views views
Watch 9 more video solutions →Practice Actors and Directors Who Cooperated At Least Three Times with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor