Table: Employees
+-------------+----------+ | Column Name | Type | +-------------+----------+ | employee_id | int | | name | varchar | | manager_id | int | | salary | int | +-------------+----------+ In SQL, employee_id is the primary key for this table. This table contains information about the employees, their salary, and the ID of their manager. Some employees do not have a manager (manager_id is null).
Find the IDs of the employees whose salary is strictly less than $30000 and whose manager left the company. When a manager leaves the company, their information is deleted from the Employees table, but the reports still have their manager_id set to the manager that left.
Return the result table ordered by employee_id.
The result format is in the following example.
Example 1:
Input: Employees table: +-------------+-----------+------------+--------+ | employee_id | name | manager_id | salary | +-------------+-----------+------------+--------+ | 3 | Mila | 9 | 60301 | | 12 | Antonella | null | 31000 | | 13 | Emery | null | 67084 | | 1 | Kalel | 11 | 21241 | | 9 | Mikaela | null | 50937 | | 11 | Joziah | 6 | 28485 | +-------------+-----------+------------+--------+ Output: +-------------+ | employee_id | +-------------+ | 11 | +-------------+ Explanation: The employees with a salary less than $30000 are 1 (Kalel) and 11 (Joziah). Kalel's manager is employee 11, who is still in the company (Joziah). Joziah's manager is employee 6, who left the company because there is no row for employee 6 as it was deleted.
Problem Overview: You are given an Employees table containing employee_id, manager_id, and salary. The task is to find employees whose salary is less than 30000, whose manager_id is not NULL, and whose manager no longer exists in the table. In other words, the employee references a manager ID that is missing from the employee list.
Approach 1: Self-Join to Find Missing Managers (O(n) time, O(1) extra space)
This method uses a self join on the Employees table. Join the table with itself where the employee’s manager_id matches another row’s employee_id. If the join fails (the manager record is missing), the joined manager fields become NULL. Filtering rows where the joined manager is NULL, while also enforcing salary < 30000 and manager_id IS NOT NULL, gives the required employees. Databases execute joins efficiently using indexes or hash joins, so the scan is typically linear in practice. This is the most direct relational approach and commonly used when working with SQL joins.
Approach 2: Using NOT EXISTS to Validate Manager Presence (O(n) time, O(1) extra space)
Instead of joining tables, this approach checks the absence of a manager using a correlated subquery. For each employee row, run a NOT EXISTS query that attempts to find a matching manager with the same employee_id. If no such row exists, the employee’s manager has left the company. Combine this condition with salary < 30000 and manager_id IS NOT NULL. Query planners often optimize NOT EXISTS into efficient anti-joins, making this solution comparable to the self-join method in performance. It is widely used in database queries where missing relationships must be detected.
Approach 3: Self Join Simulation with Lookups (O(n) time, O(n) space)
In procedural languages such as Python, Java, or JavaScript, the same idea can be implemented using a lookup structure. First iterate through the employee list and insert all employee_id values into a hash set. Then iterate again and check each employee’s manager_id. If the manager ID is not in the set, and the salary condition holds, the employee qualifies. The hash lookup runs in constant time, so the overall algorithm remains linear. This approach mirrors the relational logic of a self join but uses a hash structure instead of SQL joins.
Recommended for interviews: Interviewers typically expect the self-join or NOT EXISTS solution when the problem is presented in SQL form. Both clearly demonstrate understanding of relational data and missing foreign-key references. Showing the lookup-based approach in a programming language also proves you understand how joins translate to hash-based lookups in algorithms. Knowledge of joins and anti-joins is fundamental for problems involving hierarchical relationships or manager–employee structures, especially in join-based queries.
In this approach, we perform a self-join on the Employees table to identify employees whose manager_id is missing from the current list of employee_ids (indicating the manager has left). Moreover, we filter only those employees who have a salary less than $30,000.
This SQL query uses a LEFT JOIN to compare the manager_id of each employee with the employee_id in the Employees table. If there is no match for a manager in the table, it implies that the manager has left. The condition emp.salary < 30000 filters the employees with a salary below $30,000, and mgr.employee_id IS NULL checks if the manager has left.
SQL
The time complexity is O(n) where n is the number of employees because we scan the table and join it with itself. The space complexity is O(1) since we do not use any additional data structures.
This approach employs the NOT EXISTS clause to ensure that the manager_id of each employee does not exist in the list of employee_ids, indicating the manager has left. Employees are filtered based on their salary criterion.
In this query, the outer query selects employee_ids with a salary less than $30,000. The condition manager_id IS NOT NULL ensures we only consider those with managers. The NOT EXISTS clause checks that an employee’s manager_id does not exist in the list of current employee_ids (indicating the manager has left).
SQL
The query has a time complexity of O(n^2) due to the nested subquery for checking the non-existence of manager_ids. The space complexity is O(1) as no additional space apart from the default table storage is needed.
This approach involves a self join on the Employees table. The idea is to join the table with itself such that you can compare employee_id and manager_id. By checking for null returns in the joined table's employee_id, you can find employees whose managers no longer exist in the company database.
This Python code utilizes an in-memory SQLite database. It creates an Employees table, inserts the given data, and performs a left join to identify employees whose manager_id does not match any employee_id in the table. It then filters for salaries less than $30,000 and orders the output by employee_id.
Python
Java
JavaScript
Time Complexity: O(n*m) for the self join where n is the number of employees and m is the number of managers we are checking against.
Space Complexity: O(1) as we are not using any additional data structures outside of the database storage.
This approach uses a nested query to filter out the employees whose manager_id does not exist in the employee_id list. It also checks for salaries less than $30,000 before returning the results ordered by employee_id.
This C program uses SQLite to store and query employee data. It filters employees by salary and managers who have left the company using a subquery.
Time Complexity: O(n) for subquery execution in SQLite.
Space Complexity: O(1).
We can use a left join to connect the employee table with itself, and then filter out the employees whose salary is less than 30000 and have a superior manager who has left the company.
MySQL
We can also use a subquery to first find all the managers who have left the company, and then find the employees whose salary is less than 30000 and whose superior manager is not in the list of managers who have left the company.
MySQL
| Approach | Complexity |
|---|---|
| Self-Join to Find Missing Managers | The time complexity is O(n) where n is the number of employees because we scan the table and join it with itself. The space complexity is O(1) since we do not use any additional data structures. |
| Using NOT EXISTS to Validate Manager Presence | The query has a time complexity of O(n^2) due to the nested subquery for checking the non-existence of manager_ids. The space complexity is O(1) as no additional space apart from the default table storage is needed. |
| Approach 1: Self Join Method | Time Complexity: |
| Approach 2: Nested Query Method | Time Complexity: |
| Left Join | — |
| Subquery | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Self-Join to Detect Missing Manager | O(n) | O(1) | Best for SQL problems using relational joins |
| NOT EXISTS Anti-Join | O(n) | O(1) | When checking absence of related rows in SQL |
| Hash Set Lookup (Programming Languages) | O(n) | O(n) | When implementing outside SQL in Python, Java, or JavaScript |
| Nested Query Scan | O(n^2) | O(1) | Simple but inefficient baseline for understanding |
Employees Whose Manager Left the Company | Leetcode 1978 | Crack SQL Interviews in 50 Qs #mysql • Learn With Chirag • 6,259 views views
Watch 9 more video solutions →Practice Employees Whose Manager Left the Company with our built-in code editor and test cases.
Practice on FleetCode