570. Managers with at Least 5 Direct Reports - Detailed Explanation

Problem Statement

You are given a table (or list) of employees. Each employee record contains the following fields:

• id – a unique identifier for the employee.
• name – the employee’s name.
• salary – the employee’s salary.
• managerId – the id of the manager this employee reports to (this field can be null for employees who do not report to anyone, such as the CEO).

Your task is to return the names (or ids) of all managers who have at least 5 direct reports.

Example Inputs & Outputs

Example 1

• Input:

  [
      {"id": 1, "name": "Alice", "salary": 100000, "managerId": null},
      {"id": 2, "name": "Bob", "salary": 90000, "managerId": 1},
      {"id": 3, "name": "Charlie", "salary": 80000, "managerId": 1},
      {"id": 4, "name": "David", "salary": 75000, "managerId": 1},
      {"id": 5, "name": "Eve", "salary": 85000, "managerId": 1},
      {"id": 6, "name": "Frank", "salary": 70000, "managerId": 1}
  ]

• Output: ["Alice"]
• Explanation: Alice (id 1) has 5 direct reports (Bob, Charlie, David, Eve, Frank).

Example 2

• Input:

  [
      {"id": 1, "name": "Alice", "salary": 100000, "managerId": null},
      {"id": 2, "name": "Bob", "salary": 90000, "managerId": 1},
      {"id": 3, "name": "Charlie", "salary": 80000, "managerId": 1}
  ]

• Output: []
• Explanation: Alice has only 2 direct reports, so no manager meets the 5-report criteria.

Example 3

• Input:

  [
      {"id": 1, "name": "Alice", "salary": 100000, "managerId": null},
      {"id": 2, "name": "Bob", "salary": 90000, "managerId": 1},
      {"id": 3, "name": "Charlie", "salary": 80000, "managerId": 1},
      {"id": 4, "name": "David", "salary": 75000, "managerId": 1},
      {"id": 5, "name": "Eve", "salary": 85000, "managerId": 1},
      {"id": 6, "name": "Frank", "salary": 70000, "managerId": 1},
      {"id": 7, "name": "Grace", "salary": 65000, "managerId": 2},
      {"id": 8, "name": "Heidi", "salary": 60000, "managerId": 2},
      {"id": 9, "name": "Ivan", "salary": 55000, "managerId": 2},
      {"id": 10, "name": "Judy", "salary": 50000, "managerId": 2},
      {"id": 11, "name": "Ken", "salary": 45000, "managerId": 2}
  ]

• Output: ["Alice", "Bob"]
• Explanation:
  • Alice (id 1) has 5 direct reports (ids 2, 3, 4, 5, 6).
  • Bob (id 2) has 5 direct reports (ids 7, 8, 9, 10, 11).

Constraints

• The number of employee records can be large (efficiency matters).
• Every employee record has valid id and name fields.
• The managerId field might be null (indicating that the employee does not have a manager).

Hints Before the Solution

Hint 1

Think about how you would count the number of direct reports for each manager. Is there a way to traverse the list of employees only once to count these reports?

Hint 2

Consider using a dictionary (or hash map) where the keys are manager ids and the values are counts of direct reports. This will help you build the frequency count in one pass.

Approach 1: Brute Force

Idea

For every employee that could act as a manager, iterate through the entire list of employees to count how many times this employee’s id appears as a managerId.

Step-by-Step Walkthrough

1. For each employee (potential manager), initialize a count.
2. Loop through all employees to see if they report to the potential manager.
3. If the count is at least 5, add the manager’s name to the result.

Visual Example

Using Example 1, for Alice (id 1) you would loop through all employees and count that 5 of them have managerId = 1. For any other employee, the count will be less than 5.

Complexity

• Time Complexity: O(n²) where n is the number of employees.
• Space Complexity: O(1) (ignoring the space for the output).

Approach 2: Optimal Using a Hash Map (Dictionary)

Idea

Traverse the list of employees once and build a hash map where keys are managerIds and values are the number of direct reports. Then, iterate again through the employees to collect those whose id is a key in the map with a count ≥ 5.

Step-by-Step Walkthrough

1. Count Direct Reports:
   • Initialize an empty dictionary, say managerCount.
   • Loop over each employee:
     • If the employee’s managerId is not null, increment the count for that managerId in the dictionary.
2. Identify Managers:
   • Loop over the employee list again.
   • Check if an employee’s id exists in the dictionary and if the count is at least 5.
   • If yes, add the employee’s name to the result.

Visual Example

Using Example 3:

• First pass: Build a dictionary: {1: 5, 2: 5}.
• Second pass: Check each employee’s id. Both employee with id 1 (Alice) and id 2 (Bob) are identified as managers with at least 5 direct reports.

Complexity

• Time Complexity: O(n)
• Space Complexity: O(n) (to store the count of direct reports for each manager)

Python Code Solution

Below is a Python solution using the optimal hash map approach: