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.
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.
C++
Java
Python
C#
JavaScript
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.
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.
| 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. |
LeetCode Interview SQL Question with Detailed Explanation | Practice SQL | LeetCode 1050 • Everyday Data Science • 10,852 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