LeetCode Solutions Blog

Analyze Organization Hierarchy

Difficulty: Hard

Problem Description

Given a table of employees, each with an ID, name, manager's ID, salary, and department, determine the hierarchy levels, team sizes, and salary budgets for each employee in the organization. The CEO is at level 1, with each subsequent level increasing by 1 for their direct reports. The result should be ordered by level, then budget, and finally by employee name.

Key Insights

The top-level manager (CEO) has a null manager_id and is at level 1.
Each employee can have multiple direct reports, forming a tree-like structure.
Team size includes both direct and indirect reports.
Salary budget for a manager includes their salary and the total salaries of all their reports.
A recursive or hierarchical approach is required to traverse the employee structure.

Space and Time Complexity

Time Complexity: O(n), where n is the number of employees, due to the need to traverse the hierarchy. Space Complexity: O(n) for storing intermediate results such as levels, team sizes, and budget calculations.

Solution

Start by identifying the CEO (where manager_id is null).
Use a recursive function to traverse the employee hierarchy to calculate levels, team sizes, and budgets.
For each employee, count the total number of employees under them (direct and indirect) to obtain the team size.
Sum the salaries of the employee and all their reports to calculate the salary budget.
Finally, sort the results by level (ascending), budget (descending), and employee name (ascending).

Code Solutions

from collections import defaultdict

def analyze_hierarchy(employees):
    # Build the employee structure
    employee_dict = {}
    for emp in employees:
        employee_dict[emp['employee_id']] = {
            'name': emp['employee_name'],
            'manager_id': emp['manager_id'],
            'salary': emp['salary'],
            'level': 0,
            'team_size': 0,
            'budget': 0
        }
    
    # Function to recursively calculate level, team size, and budget
    def calculate_hierarchy(emp_id, level):
        employee = employee_dict[emp_id]
        employee['level'] = level
        
        # Initialize budget with employee's own salary
        budget = employee['salary']
        size = 1  # Counting self

        for emp in employees:
            if emp['manager_id'] == emp_id:
                # Recursive call for each direct report
                sub_budget, sub_size = calculate_hierarchy(emp['employee_id'], level + 1)
                budget += sub_budget
                size += sub_size

        employee['budget'] = budget
        employee['team_size'] = size - 1  # Exclude self
        return budget, size

    # Start with the CEO
    for emp in employees:
        if emp['manager_id'] is None:
            calculate_hierarchy(emp['employee_id'], 1)

    # Prepare the result
    result = []
    for emp_id, emp in employee_dict.items():
        result.append({
            'employee_id': emp_id,
            'employee_name': emp['name'],
            'level': emp['level'],
            'team_size': emp['team_size'],
            'budget': emp['budget']
        })

    # Sort the result
    result.sort(key=lambda x: (x['level'], -x['budget'], x['employee_name']))
    return result