Skip to main content
Talentd

Employees Whose Manager Left the Company - Solution & Explanation

EasyDatabase11 min readAsked at: Amazon, Microsoft, Google +1
Practice this problem

Problem Statement

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.

Approach Overview

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.

Approach 1: Self-Join to Find Missing Managers

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.

Code

SQL

SQL

Complexity

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.

Try this approach in the editor →

Approach 2: Using NOT EXISTS to Validate Manager Presence

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).

Code

SQL

SQL

Complexity

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.

Try this approach in the editor →

Approach 3: Approach 1: Self Join Method

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.

Code

PythonJavaJavaScript

Python

Java

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 4: Approach 2: Nested Query Method

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.

Code

CC++

C

C++

Complexity

Time Complexity: O(n) for subquery execution in SQLite.
Space Complexity: O(1).

Try this approach in the editor →

Approach 5: Left Join

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.

Code

MySQL

MySQL

Try this approach in the editor →

Approach 6: Subquery

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.

Code

MySQL

MySQL

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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: 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.

Approach 2: Nested Query Method

Time Complexity: O(n) for subquery execution in SQLite.
Space Complexity: O(1).

Left Join—
Subquery—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Self-Join to Detect Missing ManagerO(n)O(1)Best for SQL problems using relational joins
NOT EXISTS Anti-JoinO(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 ScanO(n^2)O(1)Simple but inefficient baseline for understanding

Video Solution

Employees Whose Manager Left the Company | Leetcode 1978 | Crack SQL Interviews in 50 Qs #mysql • Learn With Chirag • 6,947 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Employees Whose Manager Left the Company easy or hard?
The problem is rated Easy on LeetCode. The main requirement is understanding how to detect missing references in a table using joins or existence checks. Once you recognize it as an anti-join problem, the implementation becomes straightforward.
Employees Whose Manager Left the Company Python/Java solution
In Python or Java, first store all employee_id values in a hash set. Then iterate through employees and check whether manager_id is absent from the set while salary is below 30000. Each lookup is O(1), producing an overall O(n) time algorithm with O(n) extra space.
How to solve Employees Whose Manager Left the Company in O(n)?
Scan the Employees table and verify whether each manager_id exists. In SQL, this is done with a LEFT JOIN and filtering NULL manager matches or with a NOT EXISTS subquery. In programming languages, store all employee IDs in a hash set and check membership in O(1) time.
What is the best approach for Employees Whose Manager Left the Company?
The best approach is a SQL self-join or a NOT EXISTS anti-join. Both methods check whether an employee's manager_id exists in the Employees table. If the manager record is missing and the salary is below 30000, the employee qualifies. These approaches run in roughly O(n) time with efficient query planning.
Is Employees Whose Manager Left the Company asked at Google/Amazon/Meta?
Problems involving manager–employee relationships and missing foreign keys appear frequently in database interview rounds at companies like Amazon, Meta, and Google. Variations test knowledge of joins, anti-joins, and relational filtering conditions.
What data structure is used in Employees Whose Manager Left the Company?
In SQL solutions, the core mechanism is a self join or anti-join between rows in the same table. In programming language implementations, a hash set is commonly used to store employee IDs and quickly check whether a manager exists.
What is the time complexity of Employees Whose Manager Left the Company?
Most optimal SQL solutions run in O(n) time because the database scans the Employees table and performs indexed lookups or optimized joins. A naive nested query implementation can degrade to O(n^2) if every employee row scans the entire table again.

Ready to solve this problem?

Practice Employees Whose Manager Left the Company with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary