LeetCode 577 - Employee Bonus

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

In this problem, we are given two database tables, Employee and Bonus, and we need to produce a result table containing employees who meet one of two conditions:

Their bonus is less than 1000.
They do not have a bonus record at all.

The output should include only two columns: the employee's name and their bonus.

The Employee table stores basic employee information. Every employee has a unique empId, a name, a supervisor ID, and a salary. The Bonus table stores bonus amounts associated with employees, and each employee can have at most one bonus entry because empId is unique in this table.

The important detail is that not every employee is guaranteed to appear in the Bonus table. If an employee is missing from Bonus, it means they did not receive a bonus. Since these employees must also be included in the result, a standard inner join would not work because it would exclude employees without bonus records.

The expected output is a table containing only qualifying employees, in any order. Since ordering is unrestricted, we do not need an ORDER BY clause.

An important edge case is employees with no bonus record. A naive solution using an inner join would accidentally omit them. Another edge case is bonuses exactly equal to 1000, which should not be included because the condition is strictly less than 1000. The problem also guarantees unique employee IDs, so we do not need to handle duplicate employee records or multiple bonuses for one employee.

Approaches

Brute Force Approach

A brute-force approach would manually compare every employee with every bonus record to determine whether the employee has a matching bonus. For each employee, we would scan the entire Bonus table looking for a matching empId. If a match is found, we would check whether the bonus is less than 1000. If no match exists, we would include the employee because they received no bonus.

This approach is correct because every employee is explicitly checked against all possible bonus records. However, it is inefficient because for every employee we may scan the entire bonus table. If there are n employees and m bonus records, the total time complexity becomes O(n × m).

Optimal Approach

The key observation is that SQL databases are designed for relational matching operations through joins. Instead of manually comparing every row, we can use a LEFT JOIN between Employee and Bonus.

A LEFT JOIN ensures that every employee appears in the result, even if they have no matching bonus record. Employees without bonuses will have NULL in the bonus column. We can then filter rows using a WHERE clause:

Include employees where bonus < 1000
Include employees where bonus IS NULL

This avoids unnecessary comparisons and leverages database indexing and query optimization.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m)	O(1)	Compare every employee against every bonus record manually
Optimal	O(n + m)	O(1)	Use a LEFT JOIN and filter qualifying rows

Algorithm Walkthrough

Start with the Employee table because every employee must be considered, including those without bonuses.
Perform a LEFT JOIN with the Bonus table using the empId column. This ensures all employees remain in the intermediate result. If an employee does not have a bonus record, the bonus field becomes NULL.
Apply a filter using a WHERE clause. Keep rows where the bonus is less than 1000, or where the bonus is NULL.
Select only the required columns, name and bonus, because the problem statement only asks for these fields.
Return the result in any order, since ordering does not matter.

Why it works

The correctness of this approach depends on the behavior of LEFT JOIN. Every employee is preserved in the result, regardless of whether they have a matching bonus record. Employees with missing bonuses appear with NULL, allowing us to include them through bonus IS NULL. Meanwhile, employees with bonuses are filtered based on the condition bonus < 1000. Since these conditions exactly match the problem requirements, the query always produces the correct result.

Python Solution

Since this is a database problem, the LeetCode submission format expects an SQL query rather than executable Python code.

# This problem requires an SQL query, not Python code.

The actual implementation is expressed as an SQL statement. The core logic is the LEFT JOIN, which guarantees that employees without bonus entries are still included. The WHERE clause applies the required filtering logic by checking both low bonuses and missing bonuses.

SQL Solution

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

The query starts from Employee because we must include all employees. The LEFT JOIN matches employees to their bonuses where available. If no match exists, SQL fills the bonus field with NULL. The filtering condition then retains employees whose bonus is either less than 1000 or missing entirely.

Go Solution

Since this is a database problem, there is no Go implementation required. LeetCode expects an SQL query submission.

// This problem requires an SQL query, not Go code.

Unlike algorithmic problems, database problems on LeetCode are submitted directly as SQL statements. Therefore, there are no Go-specific concerns such as slice handling, integer overflow, or memory management.

Worked Examples

Consider the given input:

Employee Table

empId	name	supervisor	salary
3	Brad	NULL	4000
1	John	3	1000
2	Dan	3	2000
4	Thomas	3	4000

Bonus Table

empId	bonus
2	500
4	2000

After performing the LEFT JOIN:

empId	name	bonus
3	Brad	NULL
1	John	NULL
2	Dan	500
4	Thomas	2000

Now apply the filtering condition:

name	bonus	Include?	Reason
Brad	NULL	Yes	No bonus
John	NULL	Yes	No bonus
Dan	500	Yes	Bonus < 1000
Thomas	2000	No	Bonus ≥ 1000

Final result:

name	bonus
Brad	NULL
John	NULL
Dan	500

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Each table is scanned and joined efficiently
Space	O(1)	No additional data structures are explicitly created

The query performs a relational join between the Employee and Bonus tables. In practice, SQL engines optimize joins using indexes and execution plans, making this much more efficient than manual nested comparisons.

Test Cases

Since this is an SQL problem, test cases are represented conceptually as input tables and expected outputs.

# Example 1: Provided example
# Employees with NULL bonus or bonus < 1000 should appear

# Employee:
# [(3, "Brad"), (1, "John"), (2, "Dan"), (4, "Thomas")]
# Bonus:
# [(2, 500), (4, 2000)]
# Expected:
# [("Brad", None), ("John", None), ("Dan", 500)]

# Case 2: All bonuses above threshold
# Employee:
# [(1, "Alice"), (2, "Bob")]
# Bonus:
# [(1, 1500), (2, 2000)]
# Expected:
# []

# Case 3: All employees missing bonus
# Employee:
# [(1, "Alice"), (2, "Bob")]
# Bonus:
# []
# Expected:
# [("Alice", None), ("Bob", None)]

# Case 4: Bonus exactly 1000
# Employee:
# [(1, "Alice")]
# Bonus:
# [(1, 1000)]
# Expected:
# [] because condition is strictly less than 1000

# Case 5: Mixed qualifying and non-qualifying employees
# Employee:
# [(1, "Alice"), (2, "Bob"), (3, "Charlie")]
# Bonus:
# [(1, 999), (2, 1001)]
# Expected:
# [("Alice", 999), ("Charlie", None)]

Test	Why
Provided example	Verifies mixed NULL and valid bonus filtering
All bonuses above threshold	Ensures non-qualifying employees are excluded
No bonus records	Validates `LEFT JOIN` behavior
Bonus exactly 1000	Confirms strict inequality handling
Mixed employees	Tests multiple filtering paths together

Edge Cases

One important edge case occurs when an employee does not have any bonus record. This can easily break a naive implementation using an inner join because such employees would disappear from the result entirely. The implementation handles this correctly with a LEFT JOIN, which preserves all employees and assigns NULL to missing bonuses.

Another edge case is a bonus value exactly equal to 1000. Since the requirement is strictly less than 1000, employees with a bonus of exactly 1000 should not appear in the result. The query correctly uses bonus < 1000 instead of <= 1000.

A third important case is when every employee has a bonus larger than 1000. In this situation, the output should be empty. The filtering condition naturally excludes all rows, producing the correct result without requiring any special handling.