Employees Whose Manager Left the Company

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

Table: Employees

+-------------+---------+ | Column Name | Type | +-------------+---------+ | employee_id | int | | employee_name| varchar | | manager_id | int | | salary | int | +-------------+---------+ employee_id is the primary key (column with unique values) for this table. manager_id is a foreign key (reference column) to the employee_id from the Employees table. Each row of this table indicates information about an employee, including their salary and the ID of their manager.

Write a solution to find the IDs of the employees that have a salary strictly less than $30,000 and whose manager has left the company.

A manager is considered to have left the company if they are not present in the Employees table.

Return the result table ordered by employee_id.

The result format is in the following example.

• Examples
• Constraints
• Approach 1: Subquery / Set Lookup
• Approach 2: Left Join / Filter Join

Examples

Example 1:

Input: Employees table: +-------------+---------------+------------+--------+ | employee_id | employee_name | manager_id | salary | +-------------+---------------+------------+--------+ | 3 | Bob | 1 | 20000 | | 13 | Alice | 7 | 90000 | | 1 | John | -1 | 100000 | | 9 | Kite | 7 | 80000 | | 7 | Winston | 8 | 70000 | | 8 | Jonathan | 9 | 60000 | | 12 | Marry | 1 | 50000 | | 2 | Alex | 7 | 20000 | | 4 | George | 6 | 40000 | | 5 | Nancy | 6 | 40000 | | 10 | Bob | 7 | 20000 | | 11 | Jose | 7 | 20000 | +-------------+---------------+------------+--------+ Output: +-------------+ | employee_id | +-------------+ | 3 | | 2 | | 10 | | 11 | +-------------+ Explanation: The employees with IDs 3, 2, 10, and 11 have a salary strictly less than 30000. Their managers are 1, 7, 7, and 7 respectively. Managers 1 and 7 are present in the Employees table. (Note: The example output provided in the original problem statement appears to contradict the text description regarding the manager’s presence. The solutions below follow the text description logic: manager_id must NOT be in the Employees table).

Constraints

500 <= Employees table row count <= 2000

Subquery / Set Lookup

Intuition We need to identify employees who earn less than $30,000 and whose manager is not listed in the Employees table. This can be efficiently solved by first collecting all valid employee IDs into a set (or a subquery list) and then filtering the employees based on the salary condition and checking if their manager ID exists in that set.

Steps

• Collect all existing employee_id values from the Employees table into a collection (Set in programming languages, subquery in SQL).
• Iterate through the Employees table.
• For each employee, check if their salary is less than 30000.
• Additionally, check if their manager_id is NOT present in the collection of valid employee IDs.
• If both conditions are met, include the employee_id in the result.
• Sort the result by employee_id.

import pandas as pd

def find_employees(employees: pd.DataFrame) -> pd.DataFrame:
    # Get all valid employee IDs
    valid_ids = set(employees['employee_id'].unique())
    
    # Filter employees with salary < 30000 and manager_id not in valid_ids
    result = employees[
        (employees['salary'] < 30000) & 
        (~employees['manager_id'].isin(valid_ids))
    ]
    
    # Return only the employee_id column, sorted
    return result[['employee_id']].sort_values(by='employee_id').reset_index(drop=True)

Complexity

• Time: O(N) where N is the number of rows in the Employees table. We iterate through the table once to build the set and once to filter.
• Space: O(N) to store the set of valid employee IDs.
• Notes: Using a Set (or hash table) provides O(1) average time complexity for the lookup, making this approach very efficient.

Left Join / Filter Join

Intuition We can join the Employees table with itself on the condition that the manager_id of the first table matches the employee_id of the second table. If a manager has left the company, the join will result in NULL values for the second table’s columns. We then filter for these NULL cases along with the salary constraint.

Steps

• Perform a Left Join of the Employees table (aliased as E1) with itself (aliased as E2) on E1.manager_id = E2.employee_id.
• Filter the joined result where E2.employee_id is NULL (indicating the manager was not found) AND E1.salary < 30000.
• Select the employee_id from E1.
• Sort the result by employee_id.

import pandas as pd

def find_employees(employees: pd.DataFrame) -> pd.DataFrame:
    # Perform a left merge (join) with itself on manager_id and employee_id
    # We use 'left' join to keep all employees from the left table
    merged = employees.merge(
        employees, 
        left_on='manager_id', 
        right_on='employee_id', 
        how='left', 
        suffixes=('', '_manager')
    )
    
    # Filter where manager_id is not found (NaN in the merged columns) and salary < 30000
    # We check if 'employee_name_manager' is NaN to detect missing manager
    result = merged[
        (merged['salary'] < 30000) & 
        (merged['employee_name_manager'].isna())
    ]
    
    # Return only the employee_id column, sorted
    return result[['employee_id']].sort_values(by='employee_id').reset_index(drop=True)

Complexity

• Time: O(N) on average. Building the map takes O(N), and iterating through the list takes O(N) with O(1) lookups.
• Space: O(N) to store the map of employees.
• Notes: This approach is logically equivalent to the Subquery/Set Lookup approach but uses a Join paradigm which can be more intuitive for those thinking in relational terms.