This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is 690 on LeetCode. Employee importance.

Tag: “BFS”, “DFS”, “queue”

Given a data structure that holds employee information, it contains the employee’s unique ID, importance, and direct subordinate ids.

For example, employee 1 is the leader of employee 2, and employee 2 is the leader of employee 3. Their corresponding importance is 15, 10, 5. Therefore, the data structure of employee 1 is [1, 15, [2]], that of employee 2 is [2, 10, [3]], and that of employee 3 is [3, 5, []]. Note that although employee 3 is also a subordinate of employee 1, it is not reflected in employee 1’s data structure because it is not a direct subordinate.

Now enter the information of all employees in a company, along with a single employee ID, and return the sum of the importance of that employee and all of his subordinates.

Example:

Input: [[1, 5, [2, 3]], [2, 3, []], [3, 3, []], 1 Output: 11 Explanation: The importance of Employee 1 is 5, he has two direct subordinates 2 and 3, and the importance of 2 and 3 is 3. So the total importance of employee 1 is 5 + 3 + 3 = 11.Copy the code

Tip:

  • An employee can have at most one direct leader, but can have more than one direct subordinate
  • The number of employees does not exceed 2000.

Recursive/DFS

An intuitive way to do this is to write a recursive function to count the sum of certain employees.

Statistical importanceimportanceimportance value and immediate subordinates importanceimportanceimportance values. And if a subordinate has a subordinate, recurse the process.

Code:

class Solution {
    Map<Integer, Employee> map = new HashMap<>();
    public int getImportance(List<Employee> es, int id) {
        int n = es.size();
        for (int i = 0; i < n; i++) map.put(es.get(i).id, es.get(i));
        return getVal(id);
    }
    int getVal(int id) {
        Employee master = map.get(id);
        int ans = master.importance;
        for (int oid : master.subordinates) {
            Employee other = map.get(oid);
            ans += other.importance;
            for (int sub : other.subordinates) ans += getVal(sub);
        }
        returnans; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

The iteration/BFS

Another approach is to use a “queue” to store all of the EmployeeEmployeeEmployee objects to be computed, count them each time they pop up, and add their “subordinates” to the end of the queue.

Code:

class Solution {
    public int getImportance(List<Employee> es, int id) {
        int n = es.size();
        Map<Integer, Employee> map = new HashMap<>();
        for (int i = 0; i < n; i++) map.put(es.get(i).id, es.get(i));
        int ans = 0;
        Deque<Employee> d = new ArrayDeque<>();
        d.addLast(map.get(id));
        while(! d.isEmpty()) { Employee poll = d.pollFirst(); ans += poll.importance;for (intoid : poll.subordinates) { d.addLast(map.get(oid)); }}returnans; }}Copy the code
  • Time complexity: O(n)O(n)O(n)
  • Space complexity: O(n)O(n)O(n)

The last

This is No.690 of our “Brush through LeetCode” series of articles. The series started on 2021/01/01, and there are 1916 questions in LeetCode by the start date.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.