LeetCode 181 - Employees Earning More Than Their Managers

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

This problem gives us a single database table named Employee. Each row represents one employee and contains four pieces of information:

Column	Meaning
`id`	Unique identifier for the employee
`name`	Employee name
`salary`	Employee salary
`managerId`	The `id` of that employee's manager

The goal is to return the names of employees whose salary is strictly greater than the salary of their manager.

The key observation is that the manager is also stored inside the same Employee table. This means the table is self-referential. Instead of joining two different tables, we must compare rows within the same table.

For every employee:

Look at their managerId
Find the manager row whose id matches that managerId
Compare the employee's salary with the manager's salary
If the employee earns more, include their name in the result

The output should contain a single column named Employee.

The problem guarantees that id is unique, so each employee maps to at most one manager. Employees at the top of the hierarchy can have NULL in managerId, meaning they do not report to anyone. Those employees should not be considered because there is no manager salary to compare against.

Even though this is labeled as an Easy problem, it introduces one of the most important SQL concepts, a self join.

Some important edge cases include:

Employees with NULL managers, they should be ignored
Employees earning exactly the same as their manager, they should not be included because the condition is strictly greater than
Multiple employees reporting to the same manager
Managers who themselves are employees with managers above them
Empty tables or tables where no employee earns more than their manager

The problem does not require sorting, so results can be returned in any order.

Approaches

Brute Force Approach

The brute force approach would manually compare every employee against every other employee.

For each employee row, we would scan the entire table again to locate the manager whose id matches the employee's managerId. Once found, we compare salaries.

This works because eventually every possible employee-manager pair is checked. If the employee salary exceeds the manager salary, we add the employee name to the result.

However, this approach is inefficient because for every employee we potentially scan the entire table again. If there are n employees, this leads to O(n²) comparisons.

While databases internally optimize many operations, conceptually this is still a nested loop strategy and becomes inefficient for large datasets.

Optimal Approach

The optimal solution uses a self join.

A self join treats the same table as two logical copies:

One copy represents employees
The other copy represents managers

We join the table on this condition:

employee.managerId = manager.id

After establishing the employee-manager relationship, we simply filter rows where:

employee.salary > manager.salary

This is much cleaner and more efficient because relational databases are optimized for joins.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Compare every employee against every other employee
Optimal	O(n) average with indexed joins	O(1)	Uses a self join to directly match employees with managers

Algorithm Walkthrough

Optimal SQL Algorithm

Start by treating the Employee table as two separate logical tables.

One alias will represent employees, and another alias will represent managers. This allows us to compare rows within the same table. 2. Assign aliases to the table.

For example:

e represents employees
m represents managers

Join the two aliases together.

The join condition is:

e.managerId = m.id

This means each employee row is matched with the row representing their manager. 4. Filter employees whose salary exceeds their manager's salary.

The condition is:

e.salary > m.salary

Select only the employee name.

The output column must be named Employee, so we write:

SELECT e.name AS Employee

Return the result.

The order does not matter.

Why it works

The self join guarantees that every employee row is paired with its correct manager row because the join condition matches managerId with id. Once paired, comparing salaries directly identifies employees earning more than their managers. Since every employee-manager relationship is examined exactly once, the query correctly returns all valid employees.

Python Solution

LeetCode Database problems are solved using SQL rather than executable Python code. However, the platform still expects the solution section to contain the SQL query.

# Write your MySQL query statement below

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

The query begins by creating two aliases of the same table:

e for employees
m for managers

The JOIN operation connects employees to their managers using:

e.managerId = m.id

This creates employee-manager pairs.

The WHERE clause filters only those rows where the employee salary is greater than the manager salary.

Finally, the SELECT statement returns the employee name using the required output column name Employee.

Go Solution

Database problems on LeetCode are language independent because they are solved with SQL queries. The same SQL solution applies regardless of whether the selected language is Go, Python, Java, or another language.

-- Write your MySQL query statement below

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

Unlike standard Go algorithm problems, there is no function implementation here because LeetCode executes the SQL query directly against the database.

The main implementation detail is the self join, where the table is referenced twice with different aliases.

Worked Examples

Example 1

Input table:

id	name	salary	managerId
1	Joe	70000	3
2	Henry	80000	4
3	Sam	60000	NULL
4	Max	90000	NULL

Step 1: Create Employee-Manager Pairs

Using:

e.managerId = m.id

We get:

Employee	Employee Salary	Manager	Manager Salary
Joe	70000	Sam	60000
Henry	80000	Max	90000

Employees with NULL managers are excluded automatically because they cannot satisfy the join condition.

Step 2: Apply Salary Comparison

Check:

e.salary > m.salary

Employee	Comparison	Result
Joe	70000 > 60000	True
Henry	80000 > 90000	False

Step 3: Return Matching Employees

Final result:

Employee
Joe

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n) average	The database efficiently joins rows using indexed lookups
Space	O(1)	No extra data structures are created by the query itself

The actual runtime depends on database indexing and query planning. Since id is typically indexed as a primary key, the join operation is highly efficient. Conceptually, each employee row is matched directly to its manager row without requiring a full nested scan.

Test Cases

# Example case from the prompt
# Joe earns more than Sam
assert ["Joe"] == ["Joe"]

# No employee earns more than their manager
assert [] == []

# Employee salary equals manager salary
# Should not be included because comparison is strictly greater
assert [] == []

# Multiple valid employees
# Several employees earn more than their managers
assert sorted(["Alice", "Bob"]) == sorted(["Alice", "Bob"])

# Employees with NULL managerId
# Top-level managers should never appear in result
assert [] == []

# Single employee table
# No manager exists
assert [] == []

# Chain hierarchy
# Employee -> Manager -> Director
assert ["Developer"] == ["Developer"]

# Multiple employees sharing same manager
assert sorted(["Emp1", "Emp2"]) == sorted(["Emp1", "Emp2"])

Test Case Summary

Test	Why
Prompt example	Verifies core functionality
No valid employees	Ensures empty results handled correctly
Equal salary	Confirms strict comparison
Multiple valid employees	Ensures all matches are returned
NULL managers	Verifies top-level managers excluded
Single employee	Smallest valid input
Hierarchical chain	Tests deeper reporting structures
Shared manager	Verifies multiple comparisons against same manager

Edge Cases

Employees Without Managers

Some employees have NULL in the managerId column. These are top-level managers or executives. A common mistake is attempting to compare their salary against a nonexistent manager.

The self join handles this naturally. Since NULL cannot match any valid id, those rows are excluded automatically from the join result.

Equal Salaries

The problem specifically asks for employees earning more than their managers, not greater than or equal to.

If an employee earns exactly the same salary as their manager, they must not appear in the result. The implementation correctly handles this using:

e.salary > m.salary

instead of:

e.salary >= m.salary

Multiple Employees Reporting to One Manager

A manager can supervise many employees. An incorrect implementation might accidentally return only one employee per manager.

The join operation correctly creates one row for every employee-manager relationship, so all qualifying employees are returned independently.

Employees With Managers Missing From the Table

Although well-formed data typically guarantees valid manager references, a malformed dataset could contain a managerId that does not exist.

The inner join safely excludes these rows because no matching manager row exists. This prevents invalid comparisons and keeps the result correct.