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.
In #181 Employees Earning More Than Their Managers, the goal is to identify employees whose salary exceeds that of their direct manager. The key observation is that both employees and managers exist in the Employee table, meaning the problem can be solved by comparing rows within the same table.
A common strategy is to perform a self join, where the table is joined with itself. One alias represents the employee while the other represents the manager. By linking the employee’s managerId with the manager’s id, you can directly compare their salaries. After establishing this relationship, filter the results to keep only those employees whose salary is greater than their manager’s.
This approach is efficient because it leverages relational database operations designed for such comparisons. The query scans and joins records once, making it practical for typical database sizes.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Self Join on Employee Table | O(n) | O(1) |
Frederik Müller
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.
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.
1SELECT e1.name AS Employee FROM Employee e1 JOIN Employee e2 ON e1.managerId = e2.id WHERE e1.salary > e2.salaryThe 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.
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.
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.
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4using namespace std;
5
vector<string> findHighEarners(vector<vector<int>>& employees) {
unordered_map<int, int> managerSalaries;
vector<string> highEarners;
for (const auto& emp : employees) {
managerSalaries[emp[0]] = emp[2]; // emp[0] is id, emp[2] is salary
}
for (const auto& emp : employees) {
int managerId = emp[3]; // emp[3] is managerId
if (managerId != -1 && emp[2] > managerSalaries[managerId]) { // salary comparison
highEarners.push_back(emp[1]); // emp[1] is name
}
}
return highEarners;
}
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
A self join is needed because the manager information exists in the same Employee table as regular employees. By creating two aliases of the same table, you can compare an employee's salary with their manager's salary within a single query.
While this exact question may not always appear, similar SQL join problems are common in technical interviews at large tech companies. Interviewers often test a candidate's understanding of joins, filtering, and relational data comparisons.
The optimal approach is to use a SQL self join. By joining the Employee table with itself, you can match each employee to their manager using the managerId and id columns, then filter rows where the employee's salary is greater than the manager's salary.
The problem primarily relies on relational database concepts, specifically self joins. Since both employees and managers are stored in the same table, joining the table with itself allows direct comparison between employee and manager records.
The C++ solution uses an unordered_map to store each manager's salary using their ID. During the second iteration, it checks if an employee's salary is greater than their manager's salary. If true, the employee's name is added to the result vector highEarners.