LeetCode 1978 - Employees Whose Manager Left the Company
The problem is asking us to find employees in a company who meet two specific conditions. First, their salary must be strictly less than $30,000.
Difficulty: 🟢 Easy
Topics: Database
Solution
Problem Understanding
The problem is asking us to find employees in a company who meet two specific conditions. First, their salary must be strictly less than $30,000. Second, their manager has left the company, meaning there is no corresponding row for the manager in the Employees table even though the manager_id field in the employee's record still references that manager. The input is a single SQL table called Employees that contains columns for employee_id, name, manager_id, and salary. Some employees may not have a manager, in which case the manager_id is null. The expected output is a table containing only the employee_id of employees who satisfy both conditions, sorted in ascending order.
Key points include recognizing that "manager left the company" does not mean manager_id is null; it means that the manager_id references an employee_id that no longer exists in the table. The table may contain multiple employees without a manager, employees whose managers are still in the company, and employees whose managers have left. Edge cases involve employees with null manager_id, employees earning exactly $30,000, and employees whose manager ID points to a non-existent employee. The problem guarantees the employee_id is unique and that each employee's record contains valid integer fields for employee_id, manager_id, and salary.
Approaches
The brute-force approach involves checking each employee who earns less than $30,000 and then scanning the entire Employees table to see if their manager_id exists. If the manager does not exist, the employee satisfies the conditions. This works correctly because it explicitly verifies that the manager has left. However, it is inefficient because it requires nested checks for each employee, which becomes costly as the table grows.
The optimal approach leverages a SQL LEFT JOIN between the Employees table and itself. By joining on employee.manager_id = manager.employee_id, we can identify which employees have a missing manager by checking for nulls in the join result. This avoids scanning the table multiple times and executes efficiently using database indexes.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n^2) | O(1) | Check each employee against all employees to see if the manager exists |
| Optimal | O(n) | O(n) | Use a self join to directly identify missing managers in one query |
Algorithm Walkthrough
- Select employees whose salary is strictly less than $30,000. This immediately filters out any employees that cannot satisfy the salary condition.
- Perform a
LEFT JOINon theEmployeestable with itself, matchingemployee.manager_idtomanager.employee_id. This join allows us to see if the manager exists in the table. - In the result of the join, look for rows where
manager.employee_idis null. These represent employees whose manager has left the company. - Select only the
employee_idcolumn from the filtered result, as this is the required output format. - Order the final results by
employee_idin ascending order to satisfy the problem's requirement.
Why it works: The self join ensures that every employee's manager is explicitly checked against the existing employees in the table. Null values in the joined manager columns indicate that the manager is no longer present, correctly identifying employees whose managers have left. The salary filter ensures that only employees below $30,000 are considered, so both conditions are met simultaneously.
Python Solution
# This problem is SQL-based, but if we were to simulate it in Python
from typing import List, Dict
class Solution:
def employeesWithManagerLeft(self, employees: List[Dict]) -> List[int]:
# Build a set of existing employee_ids for quick lookup
existing_ids = {emp['employee_id'] for emp in employees}
result = []
for emp in employees:
if emp['salary'] < 30000 and emp['manager_id'] is not None:
if emp['manager_id'] not in existing_ids:
result.append(emp['employee_id'])
return sorted(result)
This Python implementation simulates the SQL approach. First, it constructs a set of all current employee IDs, which allows O(1) lookups. Then, it iterates over each employee, checking if the salary is below $30,000 and the manager_id is not in the set of current employees. Any matching employee IDs are appended to the result list, which is finally sorted before returning.
Go Solution
package main
import "sort"
type Employee struct {
EmployeeID int
Name string
ManagerID *int
Salary int
}
func EmployeesWithManagerLeft(employees []Employee) []int {
existingIDs := make(map[int]bool)
for _, emp := range employees {
existingIDs[emp.EmployeeID] = true
}
var result []int
for _, emp := range employees {
if emp.Salary < 30000 && emp.ManagerID != nil {
if !existingIDs[*emp.ManagerID] {
result = append(result, emp.EmployeeID)
}
}
}
sort.Ints(result)
return result
}
In Go, we handle nullable manager IDs using pointers. The map existingIDs allows quick lookup of existing employees. We iterate through the employee slice and append IDs to the result slice only if the employee meets both conditions. Finally, we sort the slice of IDs.
Worked Examples
Consider the example:
Employees:
+-------------+-----------+------------+--------+
| 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 |
Step 1: Identify employees with salary < 30000 → employee 1 and 11
Step 2: Check if their manager exists: employee 1’s manager (11) exists, employee 11’s manager (6) does not exist
Step 3: Only employee 11 satisfies both conditions
Step 4: Output [11]
| Step | Employee ID | Salary Check | Manager Exists | Result |
|---|---|---|---|---|
| 1 | 1 | <30000 | Yes | Exclude |
| 1 | 11 | <30000 | No | Include |
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n) | Building the set/map and iterating over employees both take linear time |
| Space | O(n) | We store all existing employee IDs in a set/map for fast lookup |
The linear time complexity arises because each employee is checked exactly once, and lookups in the set or map take constant time. The space complexity is linear because the set/map stores all employee IDs.
Test Cases
# test cases
employees1 = [
{'employee_id': 3, 'name': 'Mila', 'manager_id': 9, 'salary': 60301},
{'employee_id': 12, 'name': 'Antonella', 'manager_id': None, 'salary': 31000},
{'employee_id': 13, 'name': 'Emery', 'manager_id': None, 'salary': 67084},
{'employee_id': 1, 'name': 'Kalel', 'manager_id': 11, 'salary': 21241},
{'employee_id': 9, 'name': 'Mikaela', 'manager_id': None, 'salary': 50937},
{'employee_id': 11, 'name': 'Joziah', 'manager_id': 6, 'salary': 28485}
]
sol = Solution()
assert sol.employeesWithManagerLeft(employees1) == [11] # Example case
employees2 = [
{'employee_id': 1, 'name': 'Alice', 'manager_id': None, 'salary': 29000},
{'employee_id': 2, 'name': 'Bob', 'manager_id': 3, 'salary': 25000}
]
assert sol.employeesWithManagerLeft(employees2) == [2] # Manager does not exist
employees3 = [
{'employee_id': 1, 'name': 'Alice', 'manager_id': None, 'salary': 30000},
{'employee_id': 2, 'name': 'Bob', 'manager_id': 1, 'salary': 29999}
]
assert sol.employeesWithManagerLeft(employees3) == [] # Manager exists, salary < 30000 only fails
employees4 = [] # empty table
assert sol.employeesWithManagerLeft(employees4) == []
employees5 = [
{'employee_id': 1, 'name': 'Alice', 'manager_id': None, 'salary': 10000},
{'employee_id': 2, 'name': 'Bob', 'manager_id': None, 'salary': 20000}
]
assert sol.employeesWithManagerLeft(employees5) == [] # no managers left
| Test | Why |
|---|---|
| Example case | Validates the basic problem requirements |
| Manager |