Table: Teacher
+-------------+------+ | Column Name | Type | +-------------+------+ | teacher_id | int | | subject_id | int | | dept_id | int | +-------------+------+ (subject_id, dept_id) is the primary key (combinations of columns with unique values) of this table. Each row in this table indicates that the teacher with teacher_id teaches the subject subject_id in the department dept_id.
Write a solution to calculate the number of unique subjects each teacher teaches in the university.
Return the result table in any order.
The result format is shown in the following example.
Example 1:
Input: Teacher table: +------------+------------+---------+ | teacher_id | subject_id | dept_id | +------------+------------+---------+ | 1 | 2 | 3 | | 1 | 2 | 4 | | 1 | 3 | 3 | | 2 | 1 | 1 | | 2 | 2 | 1 | | 2 | 3 | 1 | | 2 | 4 | 1 | +------------+------------+---------+ Output: +------------+-----+ | teacher_id | cnt | +------------+-----+ | 1 | 2 | | 2 | 4 | +------------+-----+ Explanation: Teacher 1: - They teach subject 2 in departments 3 and 4. - They teach subject 3 in department 3. Teacher 2: - They teach subject 1 in department 1. - They teach subject 2 in department 1. - They teach subject 3 in department 1. - They teach subject 4 in department 1.
This approach utilizes hash maps (or dictionaries) to store the relationship between teachers and the unique subjects they teach. The usage of sets facilitates the storage of unique subject IDs for each teacher. After accumulating the subjects for each teacher, counting the number of unique subjects can easily be done by checking the length of each set.
This method will efficiently group, count, and return the results.
This Python solution uses a defaultdict of sets to accumulate subject IDs for each teacher. The key point here is using a set, which inherently ensures that only unique subjects are stored. After building the map of teacher ID to subject sets, we simply count the number of unique subjects by measuring the length of each set corresponding to a teacher and prepare the result list.
JavaScript
Time Complexity: O(n), where n is the number of records in the input table, assuming average O(1) time complexity for set operations.
Space Complexity: O(m), where m is the number of unique (teacher_id, subject_id) pairs.
This approach imitates SQL operations by using arrays or similar data structures to first group data by teacher and then reducing the grouped data to count the unique subjects for each group. This approach can use sorting and manual iteration to simulate a GROUP BY operation.
In this Java solution, we simulate SQL GROUP BY and aggregation using Java collections such as HashMap and HashSet. The key for the map is the teacher ID, and the value is a set that contains unique subject IDs. The solution iterates over the input data, populating the map accordingly and then measures the size of each set to get the count of unique subjects per teacher.
C++
Time Complexity: O(n) due to single-pass processing and set operations.
Space Complexity: O(m) corresponding to unique (teacher_id, subject_id) pairs.
| Approach | Complexity |
|---|---|
| Approach 1: Using Hash Maps and Sets | Time Complexity: O(n), where n is the number of records in the input table, assuming average O(1) time complexity for set operations. |
| Approach 2: SQL-like Grouping and Aggregation | Time Complexity: O(n) due to single-pass processing and set operations. |
Number of Unique Subjects Taught by Each Teacher | Leetcode 2356 | Crack SQL Interviews in 50 Qs • Learn With Chirag • 3,114 views views
Watch 9 more video solutions →Practice Number of Unique Subjects Taught by Each Teacher with our built-in code editor and test cases.
Practice on FleetCode