Employees Earning More Than Their Managers

Difficulty: Easy | Acceptance: 73.20% | Paid: No Topics: Database

Table: Employee +-------------+---------+ | Column Name | Type | +-------------+---------+ | id | int | | name | varchar | | salary | int | | managerId | int | +-------------+---------+ id is the primary key (column with unique values) of this table. managerId is a foreign key (reference column) to id from the Employee table, and it is NULL for the top manager. Each row of this table contains information about the salary of an employee and 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.

• Examples
• Constraints
• Approach 1: Self Join
• Approach 2: Subquery

Examples

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.

Constraints

Salary is positive.

Approach 1: Self Join

Intuition We can join the Employee table with itself to match each employee with their manager based on the managerId, then compare their salaries.

Steps

• Join the Employee table with itself, aliasing the first instance as e1 (employee) and the second as e2 (manager).
• Match rows where e1.managerId equals e2.id.
• Filter the results to keep only rows where e1.salary is greater than e2.salary.
• Select the name of the employee from the resulting rows.

import pandas as pd

def find_employees(employee: pd.DataFrame) -> pd.DataFrame:
    # Merge the employee table with itself on managerId and id
    merged = employee.merge(employee, left_on='managerId', right_on='id', suffixes=('', '_manager'))
    # Filter where employee salary is greater than manager salary
    result = merged[merged['salary'] > merged['salary_manager']]
    # Return the name column
    return result[['name']]

Complexity

• Time: O(N) where N is the number of rows in the Employee table, assuming efficient indexing on the join columns.
• Space: O(N) for storing the result set.
• Notes: Self-joins are efficient for hierarchical data within a single table.

Approach 2: Subquery

Intuition Use a subquery to find the salary of the manager for each employee and compare it directly in the WHERE clause.

Steps

• Select the name from the Employee table.
• Use a WHERE clause to filter employees whose salary is greater than the salary of the employee whose ID matches their managerId.

import pandas as pd

def find_employees(employee: pd.DataFrame) -> pd.DataFrame:
    # Create a series mapping manager IDs to their salaries
    manager_salaries = employee.set_index('id')['salary']
    # Filter employees whose salary is greater than their manager's salary
    # Note: managerId can be NULL, so we need to handle that
    mask = employee.apply(lambda row: row['managerId'] is not None and row['salary'] > manager_salaries.get(row['managerId'], 0), axis=1)
    result = employee[mask]
    return result[['name']]

Complexity

• Time: O(N²) in the worst case without indexing, as the subquery may execute for each row.
• Space: O(1) auxiliary space, excluding the result set.
• Notes: The Self Join approach is generally preferred for readability and potential performance benefits with proper indexing.