Watch 10 video solutions for Actors and Directors Who Cooperated At Least Three Times, a easy level problem involving Database. This walkthrough by Everyday Data Science has 14,168 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |
