LeetCode 185 Department Top Three Salaries Solution Explained

Problem Overview: Department Top Three Salaries

LeetCode 185: Department Top Three Salaries asks us to find the employees who earn one of the top three highest distinct salaries in each department.

We are given two tables:

Employee Table

Department Table

Task: Write a SQL query to list the employee name, salary, and department name for those earning one of the top three salaries in their department.

Example Input:

Employee Table

Department Table

Expected Output:

Constraints:

• Multiple employees can have the same salary.
• Some departments may have fewer than three employees.
• Use standard SQL supported by LeetCode.

Problem Difficulty & Tags

• Difficulty: Medium
• Tags / Topics: SQL, Window Functions, Ranking, DENSE_RANK, Joins

Explanation:
This problem requires knowledge of SQL joins to combine tables, and window functions—specifically DENSE_RANK()—to rank employees by salary within each department. Handling ties and filtering the top three salaries per department makes this problem a medium-level SQL challenge.

Approach / Logic Explanation

To solve LeetCode 185: Department Top Three Salaries, we need to find the top three salaries in each department, taking ties into account. Here’s how we can approach it step by step:

1. Join the Tables

   • First, join the Employee table with the Department table on DepartmentId to get the department name for each employee.

   • This ensures each row includes the employee's name, salary, and department.

2. Rank Salaries Within Each Department

   • Use the SQL window function DENSE_RANK() to assign a rank to salaries within each department.

   • DENSE_RANK() is ideal because it handles ties without skipping ranks, unlike RANK() which can leave gaps.

   Logic:

   • Partition the data by DepartmentId.

   • Order salaries in descending order so the highest salary gets rank 1.

3. Filter for Top Three Salaries

   • After ranking, filter rows where the rank is 1, 2, or 3.

   • This ensures we include all employees whose salaries are among the top three for their department.

4. Handle Edge Cases

   • Departments with fewer than three employees will still return all employees.

   • Employees with tied salaries are correctly included in the top three because of DENSE_RANK().

Summary:

• Join Employee and Department tables.
• Rank employees by salary within each department using DENSE_RANK().
• Filter for ranks 1 to 3 to get the top three salaries.

Solution Code

Select d.name as department , e1.name as employee, e1.salary as Salary
From Employee e1 join Department d on e1.DepartmentId = d.Id
Where  3 > (select count(distinct (e2.Salary))
            from  Employee e2
            where e2.Salary > e1.Salary
            and e1.DepartmentId = e2.DepartmentId)

Explanation of the Code:

• Join Employee and Department: JOIN Department d ON e1.DepartmentId = d.Id ensures each employee row has the department name.
• Correlated Subquery: Counts how many distinct salaries in the same department are higher than the current employee's salary.

SELECT COUNT(DISTINCT e2.Salary)
FROM Employee e2
WHERE e2.Salary > e1.Salary
  AND e1.DepartmentId = e2.DepartmentId

• Filter Top 3: WHERE 3 > (subquery) ensures that employees with top three highest salaries in their department are included.

  • This naturally handles ties.
  • Departments with fewer than three employees are handled automatically.

Alternative SQL Solutions

Besides using a correlated subquery, you can solve LeetCode 185 using window functions like DENSE_RANK() or ROW_NUMBER(). These approaches can be more efficient on larger datasets.

Using DENSE_RANK()

WITH RankedSalaries AS (
    SELECT 
        e.Name AS Employee,
        e.Salary,
        d.Name AS Department,
        DENSE_RANK() OVER (PARTITION BY e.DepartmentId ORDER BY e.Salary DESC) AS SalaryRank
    FROM Employee e
    JOIN Department d ON e.DepartmentId = d.Id
)
SELECT Employee, Salary, Department
FROM RankedSalaries
WHERE SalaryRank <= 3;

Using ROW_NUMBER() (Alternative Approach)

If you want exactly 3 rows per department regardless of ties, you can use ROW_NUMBER():

WITH RankedSalaries AS (
    SELECT 
        e.Name AS Employee,
        e.Salary,
        d.Name AS Department,
        ROW_NUMBER() OVER (PARTITION BY e.DepartmentId ORDER BY e.Salary DESC) AS RowNum
    FROM Employee e
    JOIN Department d ON e.DepartmentId = d.Id
)
SELECT Employee, Salary, Department
FROM RankedSalaries
WHERE RowNum <= 3;

Note: Unlike DENSE_RANK(), ROW_NUMBER() assigns unique ranks, so if salaries are tied, only one employee may appear per rank.

Step-by-Step SQL Solution for Department Top Three Salaries

Let’s understand how the SQL query works line by line using a sample dataset.

Sample Data

Employee Table

Department Table

Query Execution Breakdown

1. Join Employee and Department Tables

FROM Employee e1
JOIN Department d ON e1.DepartmentId = d.Id

• Each employee is now associated with their department name.
• Example row: Joe | 70000 | IT

2. Correlated Subquery to Count Higher Salaries

SELECT COUNT(DISTINCT e2.Salary)
FROM Employee e2
WHERE e2.Salary > e1.Salary
  AND e1.DepartmentId = e2.DepartmentId

• For each employee e1, this counts how many distinct salaries in the same department are higher.
• Example:
  • For Joe (70000, IT): Higher salaries in IT are 90000, 85000 → count = 2
  • For Max (90000, IT): Higher salaries = 0 → count = 0

3. Filter Top 3 Salaries

WHERE 3 > (subquery)

• Only employees with fewer than 3 higher distinct salaries are included.
• This ensures employees in the top three salaries per department are selected.

Result for Sample Data

• Employees tied on salary are correctly included.
• Departments with fewer than 3 employees still return all employees.

Time and Space Complexity of the SQL Solution

Time Complexity

• The query uses a correlated subquery for each employee in the Employee table.
• If there are n employees, for each employee the subquery may iterate over all employees in the same department.
• Worst-case complexity: O(n²) (when most employees are in the same department).
• Note: For practical datasets on LeetCode, this performs efficiently due to small table sizes.

Space Complexity

• No additional storage is required besides temporary variables for joins and subquery execution.
• Space complexity: O(1) extra space (excluding database internal storage and buffers).

Optimization Note

• Using a window function (DENSE_RANK()) can reduce complexity in some SQL engines, especially for larger datasets, because it avoids repeated scans for each employee.