# LeetCode 181: Employees Earning More Than Their Managers

## Problem Restatement

We are given a table named `Employee`.

| Column | Type |
|---|---|
| id | int |
| name | varchar |
| salary | int |
| managerId | int |

Each row stores one employee. The `managerId` column points to the `id` of that employee's manager.

We need to return the names of employees who earn more than their managers. The result can be returned in any order. The official problem asks for employees whose salary is greater than their manager's salary.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Table `Employee(id, name, salary, managerId)` |
| Output | One column named `Employee` |
| Rule | Employee salary must be greater than manager salary |
| Order | Any order is accepted |

Expected output column:

```sql
Employee
```

## Examples

Input:

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

Joe's manager is Sam.

```text
Joe salary = 70000
Sam salary = 60000
```

Joe earns more than Sam, so Joe should appear in the result.

Henry's manager is Max.

```text
Henry salary = 80000
Max salary = 90000
```

Henry does not earn more than Max, so Henry should not appear.

Output:

```text
+----------+
| Employee |
+----------+
| Joe      |
+----------+
```

## First Thought: Compare Employees With Their Managers

The table contains both employees and managers.

A manager is also an employee row.

So we need to read the same table in two roles:

| Alias | Meaning |
|---|---|
| `e` | The employee |
| `m` | The manager |

Then we connect them with:

```sql
e.managerId = m.id
```

After that, we keep only rows where:

```sql
e.salary > m.salary
```

## Key Insight

This is a self join problem.

A self join means joining a table with itself. We use it when rows in the same table refer to other rows in that same table.

Here, `Employee.managerId` refers back to `Employee.id`.

So the join gives us one row containing both:

| Value | Comes from |
|---|---|
| Employee name | `e.name` |
| Employee salary | `e.salary` |
| Manager name | `m.name` |
| Manager salary | `m.salary` |

Then the comparison is direct.

## Algorithm

1. Start from `Employee` as `e`.
2. Join `Employee` again as `m`.
3. Match each employee to their manager using `e.managerId = m.id`.
4. Filter rows where `e.salary > m.salary`.
5. Return `e.name` as `Employee`.

## Correctness

The join condition:

```sql
e.managerId = m.id
```

pairs every employee with their actual manager.

After this join, `e.salary` is the employee's salary, and `m.salary` is that employee's manager's salary.

The `WHERE` condition:

```sql
e.salary > m.salary
```

keeps exactly the employees who earn more than their managers.

Employees without managers have `managerId = null`. They do not join with a manager row, so they are naturally excluded.

Therefore, every returned name satisfies the problem condition, and every employee satisfying the condition is returned.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` expected | The join can use the primary key index on `id` |
| Space | `O(k)` | The result stores qualifying employees |

Here, `n` is the number of employees, and `k` is the number of employees returned.

## Implementation

```sql
SELECT
    e.name AS Employee
FROM Employee e
JOIN Employee m
    ON e.managerId = m.id
WHERE e.salary > m.salary;
```

## Code Explanation

This gives the employee table the alias `e`:

```sql
FROM Employee e
```

This joins the same table again as `m`, meaning manager:

```sql
JOIN Employee m
    ON e.managerId = m.id
```

Now each employee row is connected to its manager row.

This condition keeps only employees who earn more:

```sql
WHERE e.salary > m.salary
```

Finally, this returns the employee name under the required output column:

```sql
SELECT
    e.name AS Employee
```

## Alternative Implementation

A `LEFT JOIN` also works, but it gives no benefit here because employees without managers cannot satisfy the salary comparison.

```sql
SELECT
    e.name AS Employee
FROM Employee e
LEFT JOIN Employee m
    ON e.managerId = m.id
WHERE e.salary > m.salary;
```

The `WHERE` condition removes rows where the manager is missing, because `e.salary > null` evaluates to unknown.

For this problem, the inner join version is cleaner.

## Testing

Test case 1:

```sql
CREATE TABLE Employee (
    id INT PRIMARY KEY,
    name VARCHAR(255),
    salary INT,
    managerId INT
);

INSERT INTO Employee (id, name, salary, managerId) VALUES
(1, 'Joe', 70000, 3),
(2, 'Henry', 80000, 4),
(3, 'Sam', 60000, NULL),
(4, 'Max', 90000, NULL);

SELECT
    e.name AS Employee
FROM Employee e
JOIN Employee m
    ON e.managerId = m.id
WHERE e.salary > m.salary;
```

Expected:

```text
+----------+
| Employee |
+----------+
| Joe      |
+----------+
```

Test case 2:

```sql
DELETE FROM Employee;

INSERT INTO Employee (id, name, salary, managerId) VALUES
(1, 'Alice', 50000, NULL);
```

Expected:

```text
+----------+
| Employee |
+----------+
```

There is no manager to compare with.

Test case 3:

```sql
DELETE FROM Employee;

INSERT INTO Employee (id, name, salary, managerId) VALUES
(1, 'Alice', 100000, 2),
(2, 'Bob', 90000, NULL);
```

Expected:

```text
+----------+
| Employee |
+----------+
| Alice    |
+----------+
```

Test case 4:

```sql
DELETE FROM Employee;

INSERT INTO Employee (id, name, salary, managerId) VALUES
(1, 'Alice', 70000, 2),
(2, 'Bob', 70000, NULL);
```

Expected:

```text
+----------+
| Employee |
+----------+
```

Equal salary does not count.