Skip to main content
Talentd

Actors and Directors Who Cooperated At Least Three Times - Solution & Explanation

EasyDatabase9 min readAsked at: Amazon, Microsoft, Google
Practice this problem

Problem Statement

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.

Approach Overview

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 1: Approach 1: Using a HashMap to Count Occurrences

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Using SQL Group By and Having Clause

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.

Code

SQL

SQL

Complexity

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.

Try this approach in the editor →

Approach 3: Group By + Having

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.

Code

MySQL

MySQL

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Using a HashMap to Count Occurrences

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.

Approach 2: Using SQL Group By and Having Clause

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.

Group By + Having—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashMap CountingO(n)O(n)When processing collaboration data in application code rather than directly in SQL
SQL GROUP BY + HAVINGO(n)O(1) additionalBest for database queries where aggregation and filtering can be handled by the SQL engine

Video Solution

LeetCode Interview SQL Question with Detailed Explanation | Practice SQL | LeetCode 1050 • Everyday Data Science • 14,972 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Actors and Directors Who Cooperated At Least Three Times easy or hard?
The problem is categorized as Easy. It mainly tests understanding of SQL aggregation with GROUP BY and HAVING or simple frequency counting with a hash map, both of which are fundamental concepts.
Actors and Directors Who Cooperated At Least Three Times Python/Java solution
In Python or Java, iterate through each record and store counts in a hash map keyed by (actor_id, director_id). Increment the count for each occurrence and collect pairs where the count is at least three. The approach runs in O(n) time and O(n) space.
How to solve Actors and Directors Who Cooperated At Least Three Times in O(n)?
Scan all rows and count occurrences of each (actor_id, director_id) pair. In SQL, use GROUP BY actor_id, director_id and filter with HAVING COUNT(*) >= 3. In programming languages, store counts in a hash map and return pairs whose count reaches three or more.
What is the best approach for Actors and Directors Who Cooperated At Least Three Times?
The most efficient approach is using SQL GROUP BY with a HAVING COUNT(*) >= 3 condition. It groups rows by actor_id and director_id and directly filters pairs that collaborated at least three times. This runs in O(n) time and leverages database aggregation efficiently.
Is Actors and Directors Who Cooperated At Least Three Times asked at Google/Amazon/Meta?
This problem is a typical SQL aggregation question similar to those used in database interviews at companies like Amazon, Meta, and Google. It tests knowledge of GROUP BY, HAVING, and basic data aggregation rather than complex algorithms.
What data structure is used in Actors and Directors Who Cooperated At Least Three Times?
The algorithmic version uses a hash map where the key is the pair (actor_id, director_id) and the value is the collaboration count. In SQL solutions, the database internally handles grouping using aggregation structures during the GROUP BY operation.
What is the time complexity of Actors and Directors Who Cooperated At Least Three Times?
The typical solution runs in O(n) time where n is the number of rows in the ActorDirector table. SQL engines scan the table and aggregate counts per (actor_id, director_id) pair. Hash map implementations in application code also run in O(n) time with O(n) space.

Ready to solve this problem?

Practice Actors and Directors Who Cooperated At Least Three Times with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary