{x}
blog image

Classes More Than 5 Students

Table: Courses

+-------------+---------+
| Column Name | Type    |
+-------------+---------+
| student     | varchar |
| class       | varchar |
+-------------+---------+
(student, class) is the primary key (combination of columns with unique values) for this table.
Each row of this table indicates the name of a student and the class in which they are enrolled.

 

Write a solution to find all the classes that have at least five students.

Return the result table in any order.

The result format is in the following example.

 

Example 1:

Input: 
Courses table:
+---------+----------+
| student | class    |
+---------+----------+
| A       | Math     |
| B       | English  |
| C       | Math     |
| D       | Biology  |
| E       | Math     |
| F       | Computer |
| G       | Math     |
| H       | Math     |
| I       | Math     |
+---------+----------+
Output: 
+---------+
| class   |
+---------+
| Math    |
+---------+
Explanation: 
- Math has 6 students, so we include it.
- English has 1 student, so we do not include it.
- Biology has 1 student, so we do not include it.
- Computer has 1 student, so we do not include it.

Solution Explanation for LeetCode 596: Classes More Than 5 Students

This problem requires finding all classes with at least five students from a Courses table. The optimal approach involves using SQL's aggregation and filtering capabilities.

Approach: Using GROUP BY and HAVING

The solution leverages SQL's GROUP BY clause to group rows based on the class column. Then, the HAVING clause filters these groups, keeping only those where the count of students (COUNT(*)) is greater than or equal to 5.

SQL Code (MySQL)

SELECT class
FROM Courses
GROUP BY class
HAVING COUNT(*) >= 5;

Explanation:

  1. SELECT class: This selects the class column, which will be the output of our query.
  2. FROM Courses: This specifies that we are querying the Courses table.
  3. GROUP BY class: This groups the rows based on the unique values in the class column. All students in the same class will be grouped together.
  4. HAVING COUNT(*) >= 5: This is the crucial part. COUNT(*) counts the number of rows (students) in each group (class). HAVING filters these groups, only keeping those where the student count is 5 or more.

Time Complexity Analysis

The time complexity of this SQL query is dominated by the GROUP BY and HAVING operations. The exact time complexity depends on the underlying database system's implementation, but it's generally considered to be O(N log N) or O(N) in the best case (depending on indexing and the database engine's optimization strategies) where N is the number of rows in the Courses table. In the worst case it could be O(N^2) if there is no proper indexing. The GROUP BY operation needs to sort (or hash) the data to group it efficiently, and the HAVING clause then filters the grouped data.

Space Complexity Analysis

The space complexity depends on the size of the intermediate result produced by the GROUP BY operation. In the worst case, if there are many distinct classes and each has many students, the space complexity could be proportional to the size of the input data, which is O(N) where N is the number of rows in the Courses table. However, in most practical scenarios where the number of distinct classes is relatively small compared to the total number of rows, space complexity would likely be lower than O(N).

This solution is efficient and directly addresses the problem using the power of SQL's aggregation and filtering capabilities. There are no alternative approaches that would significantly improve the time or space complexity in this context.