Table: Employee
+-------------+---------+ | Column Name | Type | +-------------+---------+ | id | int | | name | varchar | | salary | int | | managerId | int | +-------------+---------+ id is the primary key (column with unique values) for this table. Each row of this table indicates the ID of an employee, their name, salary, and the ID of their manager.
Write a solution to find the employees who earn more than their managers.
Return the result table in any order.
The result format is in the following example.
Example 1:
Input: Employee table: +----+-------+--------+-----------+ | id | name | salary | managerId | +----+-------+--------+-----------+ | 1 | Joe | 70000 | 3 | | 2 | Henry | 80000 | 4 | | 3 | Sam | 60000 | Null | | 4 | Max | 90000 | Null | +----+-------+--------+-----------+ Output: +----------+ | Employee | +----------+ | Joe | +----------+ Explanation: Joe is the only employee who earns more than his manager.
Problem Overview: The Employees Earning More Than Their Managers problem asks you to return the names of employees whose salary is greater than their direct manager’s salary. The table stores both employees and managers in the same dataset, so the solution requires comparing rows within the same table.
Approach 1: Self Join to Compare Salaries (O(n) time, O(1) extra space)
This is the most natural solution in SQL. Since both employees and managers exist in the same table, perform a SELF JOIN where the employee’s managerId matches the manager’s id. After joining the table with itself, compare the salary columns of the employee and the manager. If the employee’s salary is greater, select that employee’s name.
The key insight is that a self join lets you treat the same table as two logical datasets: one representing employees and the other representing managers. Databases handle this efficiently, especially when indexes exist on id or managerId. This approach runs in O(n) time for scanning and joining rows (assuming indexed joins) and uses O(1) additional space since the database engine handles the join internally.
Approach 2: HashMap for Manager Salaries (O(n) time, O(n) space)
In languages like Python or C++, you can solve the problem with a hash map. First iterate through the employee list and store each employee’s salary in a hash map keyed by employeeId. This allows constant‑time lookup of any manager’s salary later.
Next iterate through the employees again. For each employee, check whether they have a manager. If they do, perform a hash lookup using managerId to retrieve the manager’s salary and compare it with the employee’s salary. If the employee earns more, add their name to the result.
The hash map guarantees O(1) average lookup time, so the overall runtime remains O(n). The tradeoff is O(n) additional memory to store the salary mapping. This approach is common in general database-style interview problems when you must simulate relational joins using in-memory data structures.
Recommended for interviews: The SQL self join is the expected answer for database interviews because it demonstrates understanding of relational queries and table relationships. The HashMap solution shows how to replicate the same logic in application code. Mentioning both approaches shows you understand both database joins and in-memory lookup strategies.
This approach uses a self join on the Employee table to compare each employee's salary with their manager's salary. The core idea is to join the Employee table with itself where the manager ID of an employee in one instance of the table matches the ID of the manager in the other instance. We then simply select those employees where the salary is greater than that of the joined manager's.
The SQL solution uses a self join query where the Employee table is joined with itself. e1.managerId = e2.id matches each employee with its manager, and the condition e1.salary > e2.salary filters out only those employees whose salary is greater than their manager's salary.
Time Complexity: O(n^2), where n is the number of employees (due to the join operation).
Space Complexity: O(n), as it requires storing the join results.
This approach involves using a HashMap to store the salaries of managers. First, iterate over the table to fill the HashMap with manager ID as the key and the corresponding manager's salary as the value. Then, iterate over the employees again to check if their salary is greater than their manager's salary using the hashmap for comparison.
In the Python implementation, a dictionary manager_salaries is used to store the salaries of all employees, which allows quick lookup of any manager's salary. For each employee, if their salary is greater than their manager's salary (found via manager_salaries[manager_id]), they are added to the list of high_earners.
C++
Time Complexity: O(n), where n is the number of employees (as each employee is processed twice).
Space Complexity: O(n), due to the additional storage used by the hashmap.
| Approach | Complexity |
|---|---|
| Using Self Join to Compare Salaries | Time Complexity: O(n^2), where n is the number of employees (due to the join operation). |
| Using HashMap for Manager Salaries | Time Complexity: O(n), where n is the number of employees (as each employee is processed twice). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| SQL Self Join | O(n) | O(1) | Best for SQL/database interview questions where relationships exist within the same table |
| HashMap Manager Lookup | O(n) | O(n) | Useful when solving the problem in application code (Python, C++) instead of SQL |
LeetCode 181: Employees Earning More Than Their Managers [SQL] • Frederik Müller • 15,397 views views
Watch 9 more video solutions →Practice Employees Earning More Than Their Managers with our built-in code editor and test cases.
Practice on FleetCode