Sponsored
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;
}
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.