Employees Whose Manager Left the Company solution and explanation
9 more videos on this problem
Employees Whose Manager Left the Company | Leetcode 1978 | Crack SQL Interviews in 50 Qs #mysqlLearn With Chirag · 5:04 · 6K views
37. Employees whose Manager Left the Company | SQL Interview Questions and AnswersStart Practicing · 4:46 · 4K views
LeetCode 1978 "Employees Whose Manager Left" Interview SQL Question with Detailed ExplanationEveryday Data Science · 6:25 · 3K views
LeetCode 1978: Employees Whose Manager Left the Company [SQL]Frederik Müller · 8:35 · 1K views
Employees Whose Manager Left the Company - Leetcode 1978 | Week 4 | Qs 18 | SQLThe Big Data Show · 13:10 · 414 views
#LeetcodeSQL50 - 37 Employees Whose Manager Left the Company | SubQueryLadle Patel · 6:54 · 270 views
Solving LeetCode 1978: 'Employees Whose Manager Left the Company' | SQL Subqueries TutorialvanAmsen · 5:07 · 147 views
1978. Employees Whose Manager Left the Company | sql | Leetcode | #leetcodeproblemsSheCodes · 7:31 · 143 views
#SQL Leetcode SQL 50 #37: Employees Whose Manager Left the Company.The Code Samples · 5:53 · 142 views
LeetCode 1978 | Employees Whose Manager Left The Company | SQL Easy | If Code Else LearnIfCodeElseLearn · 5:46 · 63 views
The problem
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.
SELECT emp.employee_id FROM Employees emp LEFT JOIN Employees mgr ON emp.manager_id = mgr.employee_id WHERE emp.salary < 30000 AND mgr.employee_id IS NULL ORDER BY emp.employee_id;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.
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.
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.
SELECT employee_id FROM Employees WHERE salary < 30000 AND manager_id IS NOT NULL AND NOT EXISTS (SELECT 1 FROM Employees e WHERE e.employee_id = Employees.manager_id) ORDER BY employee_id;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).
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 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.
import sqlite3
# Connect to SQLite database
connection = sqlite3.connect(':memory:')
cursor = connection.cursor()
cursor.execute('''
CREATE TABLE Employees(
employee_id INT PRIMARY KEY,
name VARCHAR(100),
manager_id INT,
salary INT
);
''')
# Insert the example data
cursor.executemany('''
INSERT INTO Employees (employee_id, name, manager_id, salary) VALUES (?, ?, ?, ?)
''', [
(3, 'Mila', 9, 60301),
(12, 'Antonella', None, 31000),
(13, 'Emery', None, 67084),
(1, 'Kalel', 11, 21241),
(9, 'Mikaela', None, 50937),
(11, 'Joziah', 6, 28485)
])
# SQL Query to get the desired result
cursor.execute('''
SELECT E1.employee_id
FROM Employees E1
LEFT JOIN Employees E2 ON E1.manager_id = E2.employee_id
WHERE E2.employee_id IS NULL AND E1.salary < 30000
ORDER BY E1.employee_id;
''')
# Fetch and display results
results = cursor.fetchall()
print(results)
# Close the connection
connection.close()import java.sql.*;
public class EmployeeManagerIssue {
public static void main(String[] args) throws SQLException {
Connection connection = DriverManager.getConnection("jdbc:sqlite::memory:");
Statement statement = connection.createStatement();
String createTableSQL = "CREATE TABLE Employees(" +
"employee_id INT PRIMARY KEY," +
"name VARCHAR(100)," +
"manager_id INT," +
"salary INT);
";
statement.execute(createTableSQL);
String insertSQL = "INSERT INTO Employees(employee_id, name, manager_id, salary) VALUES " +
"(3, 'Mila', 9, 60301)," +
"(12, 'Antonella', NULL, 31000)," +
"(13, 'Emery', NULL, 67084)," +
"(1, 'Kalel', 11, 21241)," +
"(9, 'Mikaela', NULL, 50937)," +
"(11, 'Joziah', 6, 28485);";
statement.execute(insertSQL);
String query = "SELECT E1.employee_id FROM Employees E1 " +
"LEFT JOIN Employees E2 ON E1.manager_id = E2.employee_id " +
"WHERE E2.employee_id IS NULL AND E1.salary < 30000 " +
"ORDER BY E1.employee_id;";
ResultSet rs = statement.executeQuery(query);
while(rs.next()) {
System.out.println(rs.getInt("employee_id"));
}
statement.close();
connection.close();
}
}const sqlite3 = require('sqlite3').verbose();
let db = new sqlite3.Database(':memory:', (err) => {
if (err) {
return console.error(err.message);
}
console.log('Connected to the in-memory SQlite database.');
});
db.serialize(() => {
db.run(`CREATE TABLE Employees (
employee_id INT PRIMARY KEY,
name TEXT,
manager_id INT,
salary INT
);`);
db.run(`INSERT INTO Employees (employee_id, name, manager_id, salary) VALUES
(3, 'Mila', 9, 60301),
(12, 'Antonella', NULL, 31000),
(13, 'Emery', NULL, 67084),
(1, 'Kalel', 11, 21241),
(9, 'Mikaela', NULL, 50937),
(11, 'Joziah', 6, 28485)
;`);
db.all(`SELECT E1.employee_id
FROM Employees E1
LEFT JOIN Employees E2 ON E1.manager_id = E2.employee_id
WHERE E2.employee_id IS NULL AND E1.salary < 30000
ORDER BY E1.employee_id;`, [], (err, rows) => {
if (err) {
throw err;
}
rows.forEach((row) => {
console.log(row.employee_id);
});
});
});
db.close((err) => {
if (err) {
return console.error(err.message);
}
console.log('Close the database connection.');
});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.
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 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.
#include <iostream>
#include <sqlite3.h>
void executeQuery(sqlite3* db) {
const char* sql = "SELECT employee_id FROM Employees "
"WHERE salary < 30000 AND manager_id NOT IN "
"(SELECT employee_id FROM Employees) "
"ORDER BY employee_id;";
sqlite3_stmt* stmt;
int rc = sqlite3_prepare_v2(db, sql, -1, &stmt, 0);
if (rc != SQLITE_OK) {
std::cerr << "Failed to fetch data: " << sqlite3_errmsg(db) << std::endl;
return;
}
while ((rc = sqlite3_step(stmt)) == SQLITE_ROW) {
std::cout << sqlite3_column_int(stmt, 0) << std::endl;
}
sqlite3_finalize(stmt);
}
int main() {
sqlite3* db;
int rc = sqlite3_open(":memory:", &db);
if (rc) {
std::cerr << "Cannot open database: " << sqlite3_errmsg(db) << std::endl;
return 1;
}
const char* createTableSQL = "CREATE TABLE Employees(" "employee_id INT PRIMARY KEY,name VARCHAR(100),manager_id INT,salary INT);";
rc = sqlite3_exec(db, createTableSQL, 0, 0, 0);
const char* insertSQL = "INSERT INTO Employees(employee_id, name, manager_id, salary) VALUES "
"(3, 'Mila', 9, 60301),"
"(12, 'Antonella', NULL, 31000),"
"(13, 'Emery', NULL, 67084),"
"(1, 'Kalel', 11, 21241),"
"(9, 'Mikaela', NULL, 50937),"
"(11, 'Joziah', 6, 28485);";
rc = sqlite3_exec(db, insertSQL, 0, 0, 0);
executeQuery(db);
sqlite3_close(db);
return 0;
}#include <sqlite3.h>
#include <stdio.h>
void executeQuery(sqlite3* db) {
const char* sql = "SELECT employee_id FROM Employees "
"WHERE salary < 30000 AND manager_id NOT IN "
"(SELECT employee_id FROM Employees) "
"ORDER BY employee_id;";
sqlite3_stmt* stmt;
int rc = sqlite3_prepare_v2(db, sql, -1, &stmt, 0);
if (rc != SQLITE_OK) {
printf("Failed to fetch data: %s\n", sqlite3_errmsg(db));
return;
}
while ((rc = sqlite3_step(stmt)) == SQLITE_ROW) {
printf("%d\n", sqlite3_column_int(stmt, 0));
}
sqlite3_finalize(stmt);
}
int main() {
sqlite3* db;
int rc = sqlite3_open(":memory:", &db);
if (rc) {
printf("Cannot open database: %s\n", sqlite3_errmsg(db));
return 1;
}
const char* createTableSQL = "CREATE TABLE Employees(
employee_id INT PRIMARY KEY,name VARCHAR(100), manager_id INT, salary INT);";
rc = sqlite3_exec(db, createTableSQL, 0, 0, 0);
const char* insertSQL = "INSERT INTO Employees(employee_id, name, manager_id, salary) VALUES "
"(3, 'Mila', 9, 60301),"
"(12, 'Antonella', NULL, 31000),"
"(13, 'Emery', NULL, 67084),"
"(1, 'Kalel', 11, 21241),"
"(9, 'Mikaela', NULL, 50937),"
"(11, 'Joziah', 6, 28485);";
rc = sqlite3_exec(db, insertSQL, 0, 0, 0);
executeQuery(db);
sqlite3_close(db);
return 0;
}This C++ program operates similarly to its C counterpart, setting up an in-memory SQLite database and performing a nested query to filter out employees with non-existent managers.
Time Complexity: O(n) for scalar subquery.
Space Complexity: O(1).
Complexity comparison
| 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: |
Complexity analysis
| 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 |
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.
