# LeetCode 184: Department Highest Salary

## 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 one department through `Employee.departmentId`.

We need to find employees who have the highest salary in each department. If multiple employees share the highest salary in the same department, we return all of them. The official problem asks for employees who have the highest salary in each department.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Tables `Employee` and `Department` |
| Output | Columns `Department`, `Employee`, and `Salary` |
| Rule | Return employees whose salary equals the highest salary in their department |
| Ties | Return all tied employees |
| Order | Any order is accepted |

Expected output columns:

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

## Examples

Input:

```text
Employee
+----+-------+--------+--------------+
| id | name  | salary | departmentId |
+----+-------+--------+--------------+
| 1  | Joe   | 70000  | 1            |
| 2  | Jim   | 90000  | 1            |
| 3  | Henry | 80000  | 2            |
| 4  | Sam   | 60000  | 2            |
| 5  | Max   | 90000  | 1            |
+----+-------+--------+--------------+

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

For department `IT`, the salaries are:

```text
Joe -> 70000
Jim -> 90000
Max -> 90000
```

The highest salary in `IT` is `90000`, so both `Jim` and `Max` should be returned.

For department `Sales`, the salaries are:

```text
Henry -> 80000
Sam   -> 60000
```

The highest salary in `Sales` is `80000`, so `Henry` should be returned.

Output:

```text
+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Jim      | 90000  |
| Sales      | Henry    | 80000  |
| IT         | Max      | 90000  |
+------------+----------+--------+
```

## First Thought: Find the Maximum Salary Per Department

The core task is to find, for each department, the maximum salary.

That query is:

```sql
SELECT
    departmentId,
    MAX(salary) AS salary
FROM Employee
GROUP BY departmentId;
```

This gives one row per department:

```text
departmentId -> highest salary
```

Then we need to return employees whose `(departmentId, salary)` pair matches one of those maximum pairs.

## Key Insight

This problem has two separate parts:

| Part | Purpose |
|---|---|
| Find max salary per department | Determines the top salary level in each department |
| Join employee and department names | Produces the required output columns |

The important detail is ties.

We should not choose only one employee per department. We should return every employee whose salary equals the department maximum.

So the condition is:

```sql
employee.salary = max_salary_for_that_department
```

not “first employee after sorting.”

## Algorithm

1. Group `Employee` by `departmentId`.
2. Compute `MAX(salary)` for each department.
3. Join `Employee` with `Department` to get department names.
4. Keep only employees whose `(departmentId, salary)` appears in the maximum-salary result.
5. Return department name, employee name, and salary.

## Correctness

The subquery:

```sql
SELECT
    departmentId,
    MAX(salary)
FROM Employee
GROUP BY departmentId
```

returns exactly one maximum salary for each department.

For any employee `e`, the pair:

```sql
(e.departmentId, e.salary)
```

is in the subquery result only when `e.salary` equals the maximum salary of `e.departmentId`.

Therefore, the outer query keeps exactly the employees who have the highest salary in their own department.

The join with `Department` only adds the department name. It does not change which employees qualify.

If several employees in the same department share the maximum salary, they all have the same qualifying `(departmentId, salary)` pair, so all of them are returned.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n + d)` expected | The database groups employees and joins departments |
| Space | `O(d)` | The grouped result stores one maximum salary per department |

Here, `n` is the number of employees, and `d` is the number of departments with employees.

## Implementation

```sql
SELECT
    d.name AS Department,
    e.name AS Employee,
    e.salary AS Salary
FROM Employee e
JOIN Department d
    ON e.departmentId = d.id
WHERE (e.departmentId, e.salary) IN (
    SELECT
        departmentId,
        MAX(salary)
    FROM Employee
    GROUP BY departmentId
);
```

## Code Explanation

This joins employees to their departments:

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

Now each employee row has both employee information and department information.

The subquery:

```sql
SELECT
    departmentId,
    MAX(salary)
FROM Employee
GROUP BY departmentId
```

computes the highest salary in each department.

This filter keeps only employees whose department and salary match that result:

```sql
WHERE (e.departmentId, e.salary) IN (...)
```

Finally, we return the requested columns:

```sql
SELECT
    d.name AS Department,
    e.name AS Employee,
    e.salary AS Salary
```

## Alternative Implementation With Window Function

We can also use `RANK()`.

```sql
WITH ranked AS (
    SELECT
        d.name AS Department,
        e.name AS Employee,
        e.salary AS Salary,
        RANK() OVER (
            PARTITION BY e.departmentId
            ORDER BY e.salary DESC
        ) AS rnk
    FROM Employee e
    JOIN Department d
        ON e.departmentId = d.id
)
SELECT
    Department,
    Employee,
    Salary
FROM ranked
WHERE rnk = 1;
```

`RANK()` is useful because tied salaries receive the same rank.

So if two employees share the highest salary in a department, both receive rank `1`.

## 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', 70000, 1),
(2, 'Jim', 90000, 1),
(3, 'Henry', 80000, 2),
(4, 'Sam', 60000, 2),
(5, 'Max', 90000, 1);

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

Expected:

```text
+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Jim      | 90000  |
| Sales      | Henry    | 80000  |
| IT         | Max      | 90000  |
+------------+----------+--------+
```

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', 100000, 1);
```

Expected:

```text
+-------------+----------+--------+
| Department  | Employee | Salary |
+-------------+----------+--------+
| Engineering | Alice    | 100000 |
+-------------+----------+--------+
```

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', 100000, 1),
(2, 'Bob', 100000, 1),
(3, 'Cara', 90000, 1);
```

Expected:

```text
+-------------+----------+--------+
| Department  | Employee | Salary |
+-------------+----------+--------+
| Engineering | Alice    | 100000 |
| Engineering | Bob      | 100000 |
+-------------+----------+--------+
```

Test case 4:

```sql
DELETE FROM Employee;
DELETE FROM Department;

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

INSERT INTO Employee (id, name, salary, departmentId) VALUES
(1, 'Alice', 50000, 1),
(2, 'Bob', 70000, 1),
(3, 'Cara', 60000, 2),
(4, 'Dan', 65000, 2);
```

Expected:

```text
+------------+----------+--------+
| Department | Employee | Salary |
+------------+----------+--------+
| IT         | Bob      | 70000  |
| Sales      | Dan      | 65000  |
+------------+----------+--------+
```