690. Employee Importance

recursive to add importance

time: O(e*s), e is employees, s is each employees' subordinates
space: O(e*s)

class Solution {
    int res = 0;
    public int getImportance(List<Employee> employees, int id) {
        for (Employee e : employees) {
            if (e.id == id) {
                calculate(e, employees);
            }
        }
        return res;
    }
    private void calculate(Employee e, List<Employee> employees) {
        res += e.importance;
        if (e.subordinates == null || e.subordinates.size() == 0) {
            return;
        }
        for (Integer sid : e.subordinates) {
            for (Employee se : employees) {
                if (se.id == sid) {
                    calculate(se, employees);
                }
            }
        }
    }
}

/*

recursive to add importance

time: O(e*s), e is employees, s is each employees' subordinates
space: O(e*s)
*/

use HashMap DFS

time: O(n), may cal every Employee

space: O(n)

class Solution {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> emp = new HashMap<>();
        for (Employee e : employees) {
            emp.put(e.id, e);
        }
        return cal(emp, id);
    }
    private int cal(Map<Integer, Employee> emp, int id) {
        Employee e = emp.get(id);
        int total = e.importance;
        
        for (int subId : e.subordinates) {
            total += cal(emp, subId);
        }
        return total;
    }
}

or use global variable

class Solution {
    int res = 0;
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> emp = new HashMap<>();
        for (Employee e : employees) {
            emp.put(e.id, e);
        }
        cal(emp, id);
        return res;
    }
    private void cal(Map<Integer, Employee> emp, int id) {
        Employee e = emp.get(id);
        res += e.importance;
        if (e.subordinates == null || e.subordinates.size() == 0) {
            return;
        }
        for (int subId : e.subordinates) {
            cal(emp, subId);
        }
    }
}

BFS

我想就認為是 O(n) 吧, n 是全部員工數

time: O(e*s), e is employees, s is each employees' subordinates
space: O(e*s)

class Solution {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> map = new HashMap<>();
        for (Employee e : employees) {
            map.put(e.id, e);
        }
        
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(id);
        
        int total = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int eid = queue.poll();
                Employee e = map.get(eid); 
                total += e.importance;
                for (int sid : e.subordinates) {
                    queue.offer(sid);
                }
            }
        }
        return total;
    }
    
}

or

class Solution {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> map = new HashMap<>();
        for (Employee e : employees) {
            map.put(e.id, e);
        }
        return bfs(map.get(id), map);
        
    }
    private int bfs(Employee e, Map<Integer, Employee> map) {
        int total = 0;
        Queue<Employee> queue = new LinkedList<>();
        queue.offer(e);
        
        while (!queue.isEmpty()) {
            Employee parent = queue.poll();
            total += parent.importance;
            
            for (int id : parent.subordinates) {
                queue.offer(map.get(id));
            }
        }
        return total;
    }
}

DFS another

/*
// Definition for Employee.
class Employee {
    public int id;
    public int importance;
    public List<Integer> subordinates;
};
*/

class Solution {
    int totalImportance = 0;
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> map = new HashMap<>();
        for (Employee e : employees) {
            map.put(e.id, e);
        }
        dfs(map.get(id), map);
        
        return totalImportance;
    }
    private void dfs(Employee e, Map<Integer, Employee> map) {
        if (e == null) {
            return;
        }
        totalImportance += e.importance;
        for (int id : e.subordinates) {
            Employee sub = map.get(id);
            dfs(sub, map);
        }
    }
}


/*
return the total importance value of this employee 
and all their direct and indirect subordinates.


build a map to find Employee data <id, Employee>: T: O(n)

get Employee, List<Integer> subordinates;

T: O(all subordinates.size(), all subtree value)
add this Employee'value, and all subordinates's value (use id to get sub Employee)

T: O(n + all subordinates.size())
s: O(n)
*/

or

class Solution {
    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> map = new HashMap<>();
        for (Employee e : employees) {
            map.put(e.id, e);
        }
        return dfs(map.get(id), map);
        
    }
    private int dfs(Employee e, Map<Integer, Employee> map) {
        if (e == null) {
            return 0;
        }
        int totalImportance = 0;
        totalImportance += e.importance;
        for (int id : e.subordinates) {
            Employee sub = map.get(id);
            totalImportance += dfs(sub, map);
        }
        return totalImportance;
    }
}