LeetCode 690: Employee Importance Solution in Python – A Step-by-Step Guide

What Is LeetCode 690: Employee Importance?

In LeetCode 690: Employee Importance, you’re given a list employees of Employee objects, each with an id (unique integer), importance (integer value), and subordinates (list of subordinate IDs), plus an integer id identifying a target employee. Your task is to calculate the total importance of this employee and all their direct subordinates (not recursive beyond one level). Return this sum as an integer. For example, with employees = [{id: 1, importance: 5, subordinates: [2, 3]}, {id: 2, importance: 3, subordinates: []}, {id: 3, importance: 3, subordinates: []}] and id = 1, the total is 5 + 3 + 3 = 11, so return 11. This problem tests your ability to navigate a flat hierarchy efficiently.

Problem Statement

• Input:
• employees: List of Employee objects (id, importance, subordinates).
• id: Integer (target employee ID).
• Output: An integer—total importance of employee and direct subordinates.
• Rules:
• Employee: {id (int), importance (int), subordinates (list of ints)}.
• Sum importance of employee with given id and their direct subordinates.
• Subordinates are not recursive beyond one level.
• Each employee has a unique ID.

Constraints

• 1 ≤ employees.length ≤ 2000.
• 1 ≤ employees[i].id ≤ 2000.
• 0 ≤ employees[i].importance ≤ 1000.
• 0 ≤ employees[i].subordinates.length ≤ 10.
• 1 ≤ id ≤ 2000.

Examples

• Input: employees = [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], id = 1
• Output: 11 (5 + 3 + 3)
• Input: employees = [[1, 2, [5]], [5, -3, []]], id = 1
• Output: -1 (2 + (-3))
• Input: employees = [[1, 5, []]], id = 1
• Output: 5 (No subordinates)

These examples set the hierarchy—let’s solve it!

Understanding the Problem: Summing Employee Importance

To solve LeetCode 690: Employee Importance in Python, we need to calculate the total importance of an employee with a given id and their direct subordinates from a list of Employee objects. A brute-force approach—scanning the list repeatedly—would be O(n²), inefficient for n ≤ 2000 with small subordinate lists. Since we’re traversing a shallow hierarchy (one level of subordinates), a hash map with DFS or BFS can optimize this by providing O(1) employee lookups. We’ll use:

• Best Solution (DFS with Hash Map): O(n) time, O(n) space—fast and elegant.
• Alternative Solution (BFS with Queue): O(n) time, O(n) space—intuitive and clear.

Let’s start with the DFS solution, breaking it down for beginners.

Best Solution: DFS with Hash Map

Why This Is the Best Solution

The DFS with hash map approach is the top choice for LeetCode 690 because it’s highly efficient—O(n) time with O(n) space—and uses a hash map to store employees by ID for O(1) access, then applies a simple DFS to sum the importance of the target employee and their direct subordinates in one pass. It fits constraints (n ≤ 2000) perfectly and is intuitive once you see the map logic. It’s like building a quick lookup table and then diving straight to the team’s total value!

How It Works

Think of this as a team tallier:

• Step 1: Build Hash Map:
• Map: id → Employee object for O(1) lookup.
• Step 2: DFS Function:
• Start at target id, get employee from map.
• Add employee’s importance.
• Recurse on each subordinate ID, summing their importance.
• Step 3: Return Result:
• Total importance from DFS.

It’s like a hierarchy summer—map and dive!

Step-by-Step Example

Example: employees = [[1, 5, [2, 3]], [2, 3, []], [3, 3, []]], id = 1

• Step 1: Build map:
• map = {1: (1, 5, [2, 3]), 2: (2, 3, []), 3: (3, 3, [])}.
• Step 2: DFS from id=1:
• Employee 1: Importance = 5, subordinates = [2, 3].
• DFS(2): Importance = 3, no subordinates, return 3.
• DFS(3): Importance = 3, no subordinates, return 3.
• Total = 5 + 3 + 3 = 11.
• Step 3: Return 11.
• Output: 11.

Example: employees = [[1, 2, [5]], [5, -3, []]], id = 1

• Step 1: map = {1: (1, 2, [5]), 5: (5, -3, [])}.
• Step 2: DFS from id=1:
• Employee 1: 2, subordinates = [5].
• DFS(5): -3, no subordinates, return -3.
• Total = 2 + (-3) = -1.
• Step 3: Return -1.
• Output: -1.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

class Employee:
    def __init__(self, id: int, importance: int, subordinates: List[int]):
        self.id = id
        self.importance = importance
        self.subordinates = subordinates

class Solution:
    def getImportance(self, employees: List['Employee'], id: int) -> int:
        # Step 1: Build hash map
        emp_map = {emp.id: emp for emp in employees}

        # Step 2: DFS to sum importance
        def dfs(emp_id: int) -> int:
            if emp_id not in emp_map:
                return 0
            employee = emp_map[emp_id]
            total = employee.importance
            for sub_id in employee.subordinates:
                total += dfs(sub_id)
            return total

        # Step 3: Start DFS and return result
        return dfs(id)

• Lines 1-6: Employee: Class definition.
• Line 10: Build: Hash map from id to Employee object.
• Lines 13-20: dfs:
• Base: Return 0 if id not found (though problem assumes valid id).
• Get employee, add importance, recurse on subordinates.
• Line 23: Return: Start DFS from target id.
• Time Complexity: O(n)—visit each employee once (subordinates ≤ 10).
• Space Complexity: O(n)—hash map and recursion stack.

This is like a team aggregator—map and sum!

Alternative Solution: BFS with Queue

Why an Alternative Approach?

The BFS with queue approach uses breadth-first search—O(n) time, O(n) space. It’s more intuitive for some, processing employees level-by-level with a queue, ensuring direct subordinates are summed without recursion. It’s like lining up the team and counting their contributions one-by-one!

How It Works

Picture this as a team queuer:

• Step 1: Build hash map for O(1) lookup.
• Step 2: BFS with queue:
• Start with target id, enqueue.
• Dequeue, add importance, enqueue subordinates.
• Step 3: Sum importance:
• Accumulate total while processing queue.
• Step 4: Return result.

It’s like a queue counter—line up and tally!

Step-by-Step Example

Example: Same as above

• Step 1: map = {1: (1, 5, [2, 3]), 2: (2, 3, []), 3: (3, 3, [])}.
• Step 2: BFS from id=1:
• Queue = [1], total = 0.
• Dequeue 1: total = 5, enqueue [2, 3].
• Dequeue 2: total = 8, no subordinates.
• Dequeue 3: total = 11, no subordinates.
• Step 3: Total = 11.
• Step 4: Return 11.
• Output: 11.

Code for BFS Approach

from collections import deque

class Solution:
    def getImportance(self, employees: List['Employee'], id: int) -> int:
        # Step 1: Build hash map
        emp_map = {emp.id: emp for emp in employees}

        # Step 2: BFS with queue
        if id not in emp_map:
            return 0
        queue = deque([id])
        total = 0

        while queue:
            emp_id = queue.popleft()
            employee = emp_map[emp_id]
            total += employee.importance
            for sub_id in employee.subordinates:
                queue.append(sub_id)

        # Step 3: Return total importance
        return total

• Line 1: Import deque.
• Line 6: Build: Hash map.
• Lines 9-19: BFS:
• Start queue with id, process each, enqueue subordinates.
• Line 22: Return total.
• Time Complexity: O(n)—visit each employee once.
• Space Complexity: O(n)—queue and map.

It’s a queue summer—enqueue and add!

Comparing the Two Solutions

• DFS (Best):
• Pros: O(n) time, O(n) space, elegant recursion.
• Cons: Recursion less obvious.
• BFS (Alternative):
• Pros: O(n) time, O(n) space, clear queue logic.
• Cons: Slightly more code, queue overhead.

DFS wins for elegance.

Additional Examples and Edge Cases

• Input: employees = [[1, 5, []]], id = 1
• Output: 5.
• Input: employees = [[2, 3, []]], id = 1
• Output: 0 (ID not found).

DFS handles these well.

Complexity Breakdown

• DFS: Time O(n), Space O(n).
• BFS: Time O(n), Space O(n).

DFS is optimal for simplicity.

Key Takeaways

• DFS: Hierarchy diving—smart!
• BFS: Queue lining—clear!
• Importance: Summing is fun.
• Python Tip: Maps rock—see Python Basics.

Final Thoughts: Tally That Team

LeetCode 690: Employee Importance in Python is a fun hierarchy challenge. DFS with hash map offers speed and elegance, while BFS with queue provides a clear alternative. Want more? Try LeetCode 207: Course Schedule or LeetCode 559: Maximum Depth of N-ary Tree. Ready to count? Head to Solve LeetCode 690 on LeetCode and sum that importance today!