Java 5-liner


  • 5
            int total = 0;
            public int getImportance(List<Employee> employees, int id) {
                Employee manager = employees.stream().filter(e -> e.id == id).collect(Collectors.toList()).get(0);
                total += manager.importance;
                manager.subordinates.forEach(subId -> getImportance(employees, subId));
                return total;
            }
    

  • 2
    L

    How about the time complexity?

    if we use extra space for map, the time complexity is O(n) and space complexity O(n).

    In java stream.filter solution, will it be O(n^2) time as it traverse list for each employee?


  • 3

    same idea beaten by Java 8

        int result = 0;
        public int getImportance(List<Employee> employees, int id) {
            List<Integer> subordinates = new LinkedList<>();
            int result = 0;
            for (Employee e : employees) {
                if (e.id == id) {
                    subordinates = e.subordinates;
                    result += e.importance;
                    break;
                }
            }
            if (subordinates.size() == 0) return result; 
            for (int i : subordinates) result += getImportance(employees, i);
            return result;
        }
    

  • 0

    @Yang_BU said in Java 5-liner:

    Can I ask why you need global var result outside your method?


  • 0
    This post is deleted!

  • 0
    M

  • 0
    Y

    Check my 3-line Java 8 solution using Map and reduce:

    public int getImportance(List<Employee> employees, int id) {
        Map<Integer, Employee> map = employees.stream().collect(Collectors.toMap(e -> e.id, e -> e));
        return helper(map, id);
    }
    
    private int helper(Map<Integer, Employee> map, int id) {
        return map.get(id).importance + map.get(id).subordinates.stream()
            .reduce(0, (s1, s2) -> s1 + helper(map, s2), (s1, s2) -> s1 + s2);
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.