LeetCode 185: Department Top Three Salaries

Problem Restatement

We are given two tables: Employee and Department.

Employee stores employee information.

Column	Type
id	int
name	varchar
salary	int
departmentId	int

Department stores department information.

Column	Type
id	int
name	varchar

Each employee belongs to a department through Employee.departmentId.

We need to find employees who are high earners in their department.

A high earner is an employee whose salary is in the top three unique salary values for that department. The result can be returned in any order.

Input and Output

Item	Meaning
Input	Tables `Employee` and `Department`
Output	Columns `Department`, `Employee`, and `Salary`
Rule	Keep employees whose salary is in the top three unique salaries of their department
Ties	Return all employees tied at a qualifying salary
Order	Any order is accepted

Expected output columns:

Department, Employee, Salary

Examples

Input:

Employee
+----+-------+--------+--------------+
| id | name  | salary | departmentId |
+----+-------+--------+--------------+
| 1  | Joe   | 85000  | 1            |
| 2  | Henry | 80000  | 2            |
| 3  | Sam   | 60000  | 2            |
| 4  | Max   | 90000  | 1            |
| 5  | Janet | 69000  | 1            |
| 6  | Randy | 85000  | 1            |
| 7  | Will  | 70000  | 1            |
+----+-------+--------+--------------+

Department
+----+-------+
| id | name  |
+----+-------+
| 1  | IT    |
| 2  | Sales |
+----+-------+

For department IT, the unique salaries are:

90000, 85000, 70000, 69000

The top three unique salaries are:

90000, 85000, 70000

So Max, Joe, Randy, and Will qualify.

Joe and Randy both have salary 85000, so both are included.

For department Sales, the unique salaries are:

80000, 60000

There are only two unique salaries, so both qualify.

Output:

+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Max      | 90000  |
| IT         | Joe      | 85000  |
| IT         | Randy    | 85000  |
| IT         | Will     | 70000  |
| Sales      | Henry    | 80000  |
| Sales      | Sam      | 60000  |
+------------+----------+--------+

First Thought: Sort Employees Per Department

A first idea is to sort employees in each department by salary descending and take the first three rows.

But this fails when there are ties.

For example, in IT:

Max   -> 90000
Joe   -> 85000
Randy -> 85000
Will  -> 70000
Janet -> 69000

If we take only three rows, we might get:

Max, Joe, Randy

But Will should also be included, because 70000 is the third unique salary.

So the problem is not asking for the top three employees.

It is asking for employees whose salary belongs to the top three distinct salary levels.

Key Insight

We need dense ranking inside each department.

DENSE_RANK() is the right window function because:

Function	Ties	Rank gaps
`ROW_NUMBER()`	Gives tied rows different numbers	No gaps
`RANK()`	Gives tied rows the same rank	Has gaps
`DENSE_RANK()`	Gives tied rows the same rank	No gaps

For this problem, tied salaries should share the same salary rank, and the next unique salary should get the next rank.

So we use:

DENSE_RANK() OVER (
    PARTITION BY departmentId
    ORDER BY salary DESC
)

Then we keep ranks 1, 2, and 3.

Algorithm

Join Employee with Department.
For each employee, compute a salary rank inside their department.
Use DENSE_RANK() ordered by salary DESC.
Keep only rows where the salary rank is less than or equal to 3.
Return department name, employee name, and salary.

Correctness

Inside each department, DENSE_RANK() assigns rank 1 to the highest unique salary.

All employees with that same salary receive rank 1.

The next lower unique salary receives rank 2.

The next lower unique salary receives rank 3.

Therefore, an employee has rank at most 3 exactly when their salary is one of the top three unique salary values in that department.

The final filter:

WHERE salary_rank <= 3

keeps exactly those employees.

The join with Department only provides the department name required in the output.

Complexity

Metric	Value	Why
Time	`O(n log n)`	Rows are ranked by sorting salaries within each department
Space	`O(n)`	The database may materialize ranked rows

Here, n is the number of employees.

Implementation

WITH ranked AS (
    SELECT
        d.name AS Department,
        e.name AS Employee,
        e.salary AS Salary,
        DENSE_RANK() OVER (
            PARTITION BY e.departmentId
            ORDER BY e.salary DESC
        ) AS salary_rank
    FROM Employee e
    JOIN Department d
        ON e.departmentId = d.id
)
SELECT
    Department,
    Employee,
    Salary
FROM ranked
WHERE salary_rank <= 3;

Code Explanation

This joins employees with departments:

FROM Employee e
JOIN Department d
    ON e.departmentId = d.id

This computes a rank inside each department:

DENSE_RANK() OVER (
    PARTITION BY e.departmentId
    ORDER BY e.salary DESC
) AS salary_rank

PARTITION BY e.departmentId means each department is ranked separately.

ORDER BY e.salary DESC means higher salaries get smaller rank numbers.

Then the outer query keeps only the top three salary ranks:

WHERE salary_rank <= 3

Finally, it returns the required columns:

Department,
Employee,
Salary

Alternative Implementation Without Window Functions

We can also count how many distinct salaries are greater than the current employee’s salary inside the same department.

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.departmentId = e1.departmentId
      AND e2.salary > e1.salary
);

For an employee to be in the top three unique salaries, there must be fewer than three distinct salaries above them.

For example:

Salary	Distinct salaries above	Qualifies
90000	0	yes
85000	1	yes
70000	2	yes
69000	3	no

This version is useful for older SQL environments, but the window function version is clearer.

Testing

Test case 1:

CREATE TABLE Employee (
    id INT PRIMARY KEY,
    name VARCHAR(255),
    salary INT,
    departmentId INT
);

CREATE TABLE Department (
    id INT PRIMARY KEY,
    name VARCHAR(255)
);

INSERT INTO Employee (id, name, salary, departmentId) VALUES
(1, 'Joe', 85000, 1),
(2, 'Henry', 80000, 2),
(3, 'Sam', 60000, 2),
(4, 'Max', 90000, 1),
(5, 'Janet', 69000, 1),
(6, 'Randy', 85000, 1),
(7, 'Will', 70000, 1);

INSERT INTO Department (id, name) VALUES
(1, 'IT'),
(2, 'Sales');

Expected:

+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Max      | 90000  |
| IT         | Joe      | 85000  |
| IT         | Randy    | 85000  |
| IT         | Will     | 70000  |
| Sales      | Henry    | 80000  |
| Sales      | Sam      | 60000  |
+------------+----------+--------+

Test case 2:

DELETE FROM Employee;
DELETE FROM Department;

INSERT INTO Department (id, name) VALUES
(1, 'Engineering');

INSERT INTO Employee (id, name, salary, departmentId) VALUES
(1, 'Alice', 100, 1),
(2, 'Bob', 90, 1),
(3, 'Cara', 80, 1),
(4, 'Dan', 70, 1);

Expected:

+-------------+----------+--------+
| Department  | Employee | Salary |
+-------------+----------+--------+
| Engineering | Alice    | 100    |
| Engineering | Bob      | 90     |
| Engineering | Cara     | 80     |
+-------------+----------+--------+

Test case 3:

DELETE FROM Employee;
DELETE FROM Department;

INSERT INTO Department (id, name) VALUES
(1, 'Engineering');

INSERT INTO Employee (id, name, salary, departmentId) VALUES
(1, 'Alice', 100, 1),
(2, 'Bob', 100, 1),
(3, 'Cara', 90, 1),
(4, 'Dan', 80, 1),
(5, 'Eve', 70, 1);

Expected:

+-------------+----------+--------+
| Department  | Employee | Salary |
+-------------+----------+--------+
| Engineering | Alice    | 100    |
| Engineering | Bob      | 100    |
| Engineering | Cara     | 90     |
| Engineering | Dan      | 80     |
+-------------+----------+--------+

Test case 4:

DELETE FROM Employee;
DELETE FROM Department;

INSERT INTO Department (id, name) VALUES
(1, 'Sales');

INSERT INTO Employee (id, name, salary, departmentId) VALUES
(1, 'Henry', 80000, 1),
(2, 'Sam', 60000, 1);

Expected:

+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| Sales      | Henry    | 80000  |
| Sales      | Sam      | 60000  |
+------------+----------+--------+