Problem Overview

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

Column Name Type
Id int
Name varchar
Salary int
DepartmentId int

Department Table

Column Name Type
Id int
Name varchar

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

Id Name Salary DepartmentId
1 Joe 70000 1
2 Max 90000 1
3 Randy 85000 1
4 Will 70000 1
5 Henry 80000 2
6 Sam 60000 2

Department Table

Id Name
1 IT
2

Sales

Expected Output:

Department Employee Salary
IT Max 90000
IT Randy 85000
IT Joe 70000
Sales Henry 80000
Sales Sam 60000

Constraints:

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

Department Top Three Salaries solution

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.

Step-by-Step Walkthrough

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

Sample Data

Employee Table

Id Name Salary DepartmentId
1 Joe 70000 1
2 Max 90000 1
3 Randy 85000 1
4 Will 70000 1
5 Henry 80000 2
6 Sam 60000 2

Department Table

Id Name
1 IT
2 Sales

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

  1. 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

  1. 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

Department Employee Salary
IT Max 90000
IT Randy 85000
IT Joe 70000
Sales Henry 80000
Sales Sam 60000
  • Employees tied on salary are correctly included.
  • Departments with fewer than 3 employees still return all employees.

Time & Space Complexity Analysis

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.

Mistakes to Avoid / Tips

⚠️ Warning: Using RANK() instead of DENSE_RANK() may skip ranks for tied salaries, excluding employees who should be in the top three.
❌ Error: Forgetting to count only salaries within the same department. The correlated subquery must include e1.DepartmentId = e2.DepartmentId.
💡 Hint: For larger datasets, consider using DENSE_RANK() OVER (PARTITION BY DepartmentId ORDER BY Salary DESC) to avoid repeated subquery scans.
ℹ️ Note: Departments with fewer than three employees are automatically handled by the query, so no extra condition is needed.

Related Problems

Conclusion

LeetCode 185: Department Top Three Salaries is a great exercise to practice SQL joins, correlated subqueries, and handling ties in ranking.

Key takeaways:

  • Use a correlated subquery or window functions like DENSE_RANK() to rank employees by salary within each department.
  • Always account for ties and departments with fewer than three employees.
  • This problem reinforces understanding of ranking, partitioning, and filtering in SQL queries.

By following this approach, you can efficiently retrieve the top three salaries per department, ensuring correctness and scalability for larger datasets.

Try experimenting with DENSE_RANK vs RANK and see how results differ—it’s a great way to deepen your SQL knowledge.