Watch 10 video solutions for Employees Earning More Than Their Managers, a easy level problem involving Database. This walkthrough by Frederik Müller has 15,397 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |
