# LeetCode 577: Employee Bonus

## Problem Restatement

We are given two tables: `Employee` and `Bonus`.

The task is to report each employee's `name` and `bonus` when the employee satisfies one of these conditions:

1. The employee has a bonus less than `1000`.
2. The employee has no bonus record.

Return the result table in any order. The official problem describes this as reporting the name and bonus amount of each employee whose bonus is less than `1000`; the expected result also includes employees with no bonus record, so `NULL` bonuses must be included.

## Tables

### Employee

| Column | Type | Meaning |
|---|---|---|
| `empId` | int | Employee ID |
| `name` | varchar | Employee name |
| `supervisor` | int | ID of the employee's supervisor |
| `salary` | int | Employee salary |

`empId` is unique in this table.

### Bonus

| Column | Type | Meaning |
|---|---|---|
| `empId` | int | Employee ID |
| `bonus` | int | Employee bonus amount |

`empId` is unique in this table and refers to `Employee.empId`.

## Example

Input:

`Employee`

| empId | name | supervisor | salary |
|---|---|---|---|
| 3 | Brad | null | 4000 |
| 1 | John | 3 | 1000 |
| 2 | Dan | 3 | 2000 |
| 4 | Thomas | 3 | 4000 |

`Bonus`

| empId | bonus |
|---|---|
| 2 | 500 |
| 4 | 2000 |

Output:

| name | bonus |
|---|---|
| Brad | null |
| John | null |
| Dan | 500 |

Brad and John have no row in the `Bonus` table, so their bonus is `NULL`.

Dan has a bonus of `500`, which is less than `1000`.

Thomas has a bonus of `2000`, so he is excluded.

## First Thought: Inner Join

A first attempt might be:

```sql
SELECT e.name, b.bonus
FROM Employee e
JOIN Bonus b
    ON e.empId = b.empId
WHERE b.bonus < 1000;
```

This returns employees who have a matching bonus row and whose bonus is less than `1000`.

But it misses employees with no bonus record.

For this problem, missing bonus records must appear in the result as `NULL`.

So an inner join is too restrictive.

## Key Insight

We need all employees first, then attach bonus information when it exists.

That is exactly what `LEFT JOIN` does.

A `LEFT JOIN` keeps every row from the left table. If there is no matching row in the right table, the right-side columns become `NULL`.

So we should start from `Employee` and left join `Bonus`.

Then we keep rows where:

```sql
b.bonus < 1000
```

or:

```sql
b.bonus IS NULL
```

The `IS NULL` check is necessary because SQL does not treat `NULL < 1000` as true.

## Algorithm

1. Select from `Employee`.
2. Use `LEFT JOIN` to attach matching rows from `Bonus`.
3. Match rows using `empId`.
4. Keep rows where `bonus < 1000`.
5. Also keep rows where `bonus IS NULL`.
6. Return `name` and `bonus`.

## Correctness

The query uses `Employee` as the left table. Therefore, every employee is considered, even if that employee has no matching row in `Bonus`.

For an employee with a matching bonus row, the joined row contains the actual bonus value. The `WHERE b.bonus < 1000` condition keeps exactly those employees whose bonus is less than `1000`.

For an employee without a matching bonus row, the joined `bonus` value is `NULL`. The `WHERE b.bonus IS NULL` condition keeps exactly those employees with no bonus record.

Employees with a bonus greater than or equal to `1000` fail both conditions, so they are excluded.

Therefore, the query returns exactly the employees required by the problem.

## Complexity

Let:

```text
E = number of rows in Employee
B = number of rows in Bonus
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(E + B)` | The database can scan and join the two tables using `empId` |
| Space | `O(E + B)` | The join may build or use an intermediate structure depending on the query engine |

Actual performance depends on the database engine and indexes. Since `empId` is unique in both tables, this join is straightforward.

## Implementation

```sql
SELECT
    e.name,
    b.bonus
FROM Employee AS e
LEFT JOIN Bonus AS b
    ON e.empId = b.empId
WHERE b.bonus < 1000
   OR b.bonus IS NULL;
```

## Code Explanation

This part chooses the output columns:

```sql
SELECT
    e.name,
    b.bonus
```

We need the employee name from `Employee` and the bonus amount from `Bonus`.

This part starts with all employees:

```sql
FROM Employee AS e
```

This part attaches bonus information when it exists:

```sql
LEFT JOIN Bonus AS b
    ON e.empId = b.empId
```

A `LEFT JOIN` is required because employees without a bonus row still need to be returned.

This part filters the result:

```sql
WHERE b.bonus < 1000
   OR b.bonus IS NULL;
```

The first condition keeps employees with a small bonus.

The second condition keeps employees with no bonus record.

## Testing

Sample data:

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

CREATE TABLE Bonus (
    empId INT PRIMARY KEY,
    bonus INT
);

INSERT INTO Employee (empId, name, supervisor, salary) VALUES
(3, 'Brad', NULL, 4000),
(1, 'John', 3, 1000),
(2, 'Dan', 3, 2000),
(4, 'Thomas', 3, 4000);

INSERT INTO Bonus (empId, bonus) VALUES
(2, 500),
(4, 2000);
```

Query:

```sql
SELECT
    e.name,
    b.bonus
FROM Employee AS e
LEFT JOIN Bonus AS b
    ON e.empId = b.empId
WHERE b.bonus < 1000
   OR b.bonus IS NULL;
```

Expected result:

| name | bonus |
|---|---|
| Brad | null |
| John | null |
| Dan | 500 |

Additional test cases:

| Case | Expected behavior |
|---|---|
| Employee has no bonus row | Included with `NULL` bonus |
| Employee has bonus `999` | Included |
| Employee has bonus `1000` | Excluded |
| Employee has bonus `2000` | Excluded |
| Every employee has no bonus | Every employee is included |