# 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:

```sql
Department, Employee, Salary
```

## Examples

Input:

```text
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:

```text
90000, 85000, 70000, 69000
```

The top three unique salaries are:

```text
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:

```text
80000, 60000
```

There are only two unique salaries, so both qualify.

Output:

```text
+------------+----------+--------+
| 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`:

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

If we take only three rows, we might get:

```text
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:

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

Then we keep ranks `1`, `2`, and `3`.

## Algorithm

1. Join `Employee` with `Department`.
2. For each employee, compute a salary rank inside their department.
3. Use `DENSE_RANK()` ordered by `salary DESC`.
4. Keep only rows where the salary rank is less than or equal to `3`.
5. 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:

```sql
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

```sql
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:

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

This computes a rank inside each department:

```sql
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:

```sql
WHERE salary_rank <= 3
```

Finally, it returns the required columns:

```sql
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.

```sql
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:

```sql
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:

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

Test case 2:

```sql
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:

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

Test case 3:

```sql
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:

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

Test case 4:

```sql
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:

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