Employee Importance

MediumGraph DFS · Hash Map🧩 Graph DFS LeetCode #690 ↗Updated Oct 30, 2026

Problem

Each Employee has a unique id, an integer importance and a list of the ids of their direct reports (subordinates). Given the list of all employees (in any order) and an id, return the total importance of that employee plus everyone below them in the reporting chain, direct or indirect.

Inputemployees = [[1,5,[2,3]],[2,3,[]],[3,3,[]]], id = 1Output11

Inputemployees = [[1,2,[5]],[5,-3,[]]], id = 5Output-3

1 ≤ n ≤ 2000 · 1 ≤ id ≤ 2000, all distinct · -100 ≤ importance ≤ 100 · everyone has at most one manager, no cycles

Try it yourself

Java

class Solution {
    public int getImportance(List<Employee> employees, int id) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

The reporting lines form a tree rooted at the given employee, so the answer is just a subtree sum. The only real cost is looking up an employee by id — index them in a hash map once and the traversal becomes linear.

PatternGraph DFS

Instinct Connected regions, all paths, reachability, cloning or 2-colouring a graph or grid: dive from a node, mark it, recurse into unvisited neighbours.

Memory hack Mark before you march: go deep, paint as you go, and back up only when every door is already painted.

Open the Graph DFS guide →

Approaches

Brute ForceDFS with Linear Lookup

Time O(n²)Space O(h)

Recursively add the employee's importance and the totals of each subordinate, but find every employee by scanning the whole input list. Each of the (up to n) visited employees triggers an O(n) scan.

Java

public int getImportance(List<Employee> employees, int id) {
    Employee e = findById(employees, id);
    int total = e.importance;
    for (int sub : e.subordinates) total += getImportance(employees, sub);
    return total;
}
private Employee findById(List<Employee> employees, int id) {
    for (Employee e : employees) {
        if (e.id == id) return e;
    }
    throw new IllegalArgumentException("unknown id " + id);
}

Correct and tiny, but the lookups dominate: ~4·10⁶ steps at n = 2000.

BetterSort by Id + Binary Search Lookup

Time O(n log n)Space O(n)

Copy the employees into an array sorted by id once. Every lookup is now a binary search, so visiting all reports costs O(log n) each instead of a full scan.

Java

public int getImportance(List<Employee> employees, int id) {
    Employee[] byId = employees.toArray(new Employee[0]);
    Arrays.sort(byId, (a, b) -> Integer.compare(a.id, b.id));
    return total(byId, id);
}
private int total(Employee[] byId, int id) {
    Employee e = byId[search(byId, id)];
    int sum = e.importance;
    for (int sub : e.subordinates) sum += total(byId, sub);
    return sum;
}
private int search(Employee[] byId, int id) {
    int lo = 0, hi = byId.length - 1;
    while (lo < hi) {
        int mid = (lo + hi) >>> 1;
        if (byId[mid].id < id) lo = mid + 1;
        else hi = mid;
    }
    return lo;
}

A clear speed-up without hashing, but sorting is still more work than needed.

OptimalHash Map Index + Iterative DFS

Time O(n)Space O(n)

Build id → Employee in a HashMap (O(1) lookups), then walk the reporting tree with an explicit stack, summing importances. Each employee is pushed and popped at most once, and no recursion depth limit applies even for a 2000-long chain of managers.

Java

public int getImportance(List<Employee> employees, int id) {
    Map<Integer, Employee> byId = new HashMap<>();
    for (Employee e : employees) byId.put(e.id, e);
    int total = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(id);
    while (!stack.isEmpty()) {
        Employee e = byId.get(stack.pop());
        total += e.importance;
        for (int sub : e.subordinates) stack.push(sub); // visit reports later
    }
    return total;
}

Linear time; the map is the standard trade of O(n) memory for constant lookups.

Pro tip

No visited set is needed: each employee has at most one manager, so the structure is a tree and nobody can be reached twice.

At a glance

Level	Approach	Time	Space
Brute Force	DFS with Linear Lookup	`O(n²)`	`O(h)`
Better	Sort by Id + Binary Search Lookup	`O(n log n)`	`O(n)`
Optimal	Hash Map Index + Iterative DFS	`O(n)`	`O(n)`

Common pitfalls

Summing only direct subordinates — indirect reports must be included too.
Assuming employees.get(id) works — list order has nothing to do with ids.
Forgetting importance can be negative — don't prune on “non-positive” values.

Interview tips

Identify it as a subtree sum on an implicit tree before writing code.
Call out lookup cost as the bottleneck and fix it with a hash map.
Offer BFS or iterative DFS if the interviewer worries about deep recursion.

Pattern

Index by id, then DFS/BFS → aggregating over a hierarchy given as an id-linked list of records.

My notes saved in this browser