Solution Explanation

This problem requires calculating the rank percentage of students within their respective departments based on their exam marks. The solution leverages the power of window functions in SQL to efficiently compute the rank and percentage.

Approach:

The core idea is to use the RANK() window function to assign ranks to students within each department based on their marks in descending order. The highest mark gets rank 1, and students with the same mark receive the same rank. Then, we calculate the percentage using the formula provided: (rank - 1) * 100 / (total students - 1). The IFNULL function handles the edge case where there's only one student in a department, preventing division by zero. ROUND ensures the percentage is rounded to two decimal places.

MySQL Code:

SELECT
    student_id,
    department_id,
    IFNULL(
        ROUND(
            (
                RANK() OVER (
                    PARTITION BY department_id
                    ORDER BY mark DESC
                ) - 1
            ) * 100 / (COUNT(*) OVER (PARTITION BY department_id) - 1),
            2
        ),
        0
    ) AS percentage
FROM Students;

Code Breakdown:

1. SELECT student_id, department_id: This selects the student's ID and department ID.

2. IFNULL(..., 0): This handles the case where the denominator in the percentage calculation is zero (i.e., only one student in the department). If the result of the calculation is NULL, it defaults to 0.

3. ROUND(..., 2): This rounds the calculated percentage to two decimal places.

4. (RANK() OVER (PARTITION BY department_id ORDER BY mark DESC) - 1): This is the core of the calculation.

   • PARTITION BY department_id: This divides the data into groups based on the department_id, ensuring that the ranking is done separately for each department.
   • ORDER BY mark DESC: This orders the students within each department by their marks in descending order.
   • RANK(): This assigns a rank to each student within their department based on the order defined above. Students with the same mark get the same rank.
   • -1: We subtract 1 from the rank to align with the problem's requirement of the highest-ranked student having a percentage of 0.

5. (COUNT(*) OVER (PARTITION BY department_id) - 1): This calculates the total number of students in each department minus 1, forming the denominator of the percentage calculation. COUNT(*) counts all rows within each partition (department).

Time Complexity Analysis:

The time complexity is dominated by the window functions (RANK() and COUNT()). Window functions generally have a time complexity of O(N log N) where N is the number of rows in the Students table in the worst case (due to sorting). However, database engines often optimize these operations, making the actual performance better in practice. The overall complexity can be considered O(N log N) in the worst case. The rounding and IFNULL operations add negligible extra time.

Space Complexity Analysis:

The space complexity depends on the size of the intermediate results generated by the window functions. In the worst case, this can be proportional to the input size (O(N)). However, database systems may optimize the storage of intermediate results, reducing the actual space usage.