Introduction

In this blog post, we will explore how to solve the LeetCode problem "690" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

You have a data structure of employee information, including the employee's unique ID, importance value, and direct subordinates' IDs. You are given an array of employees employees where: employees[i].id is the ID of the ith employee. employees[i].importance is the importance value of the ith employee. employees[i].subordinates is a list of the IDs of the direct subordinates of the ith employee. Given an integer id that represents an employee's ID, return the total importance value of this employee and all their direct and indirect subordinates. Example 1: Input: employees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1 Output: 11 Explanation: Employee 1 has an importance value of 5 and has two direct subordinates: employee 2 and employee 3. They both have an importance value of 3. Thus, the total importance value of employee 1 is 5 + 3 + 3 = 11. Example 2: Input: employees = [[1,2,[5]],[5,-3,[]]], id = 5 Output: -3 Explanation: Employee 5 has an importance value of -3 and has no direct subordinates. Thus, the total importance value of employee 5 is -3. Constraints: 1 <= employees.length <= 2000 1 <= employees[i].id <= 2000 All employees[i].id are unique. -100 <= employees[i].importance <= 100 One employee has at most one direct leader and may have several subordinates. The IDs in employees[i].subordinates are valid IDs.

Explanation

Here's the solution to calculate the total importance value of an employee and their subordinates:

• Build an Employee Map: Create a dictionary (hash map) to quickly look up employee information by their ID. This avoids repeatedly iterating through the employees array.
• Depth-First Search (DFS): Use DFS to traverse the employee hierarchy starting from the given employee ID. Recursively calculate the total importance by summing the importance of the current employee and the total importance of their subordinates.

• Handle Base Case: When an employee has no subordinates (or their subordinates have already been visited), simply return their importance value.

• Runtime Complexity: O(N), where N is the number of employees. Storage Complexity: O(N)

Code

    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:
        """
        Calculates the total importance value of an employee and all their direct and indirect subordinates.
        """

        employee_map = {employee.id: employee for employee in employees}

        def dfs(employee_id: int) -> int:
            """
            Performs a depth-first search to calculate the total importance.
            """
            employee = employee_map[employee_id]
            total_importance = employee.importance

            for subordinate_id in employee.subordinates:
                total_importance += dfs(subordinate_id)

            return total_importance

        return dfs(id)