Finding an Employee having the Second highest Salary for each Department using Streams in Java 8

userDlmO 0
Viewed 74

I have Employee defined as follows:

class Employee {
    private Long salary;
    private String department;

    // getters, constructor, etc.
}

There's a list of Employee.

I am trying to get an employee with the second-highest salary for each department.

I found a way to get an employee with the second-highest salary using the following code:

employeeList.stream()
    .sorted(Comparator.comparingLong(Employee::getSalary).reversed())
    .skip(1).findFirst();

and able to get the highest salary of employees by each department using

List<Employee> employeeList = // initializing the list

Map<Object, Object> topEmployeesByDept = employeeList.stream()
    .collect(groupingBy(
        e -> e.getDepartment(),
        collectingAndThen(
            maxBy(comparingLong(e -> e.getSalary())),
            Optional::get)
    ));

But I can't find a way to combine these two approaches for finding an employee with the second-highest salary for each department.

collectors java-stream java
1 Answers

To combine the two code snippets, you've provided, you need to split the data by grouping employees that belong to the same department together and then sort the Employee objects mapped to each department.

That's how it might be implemented:

List<Employee> employeeList = // initializing the list
        
Map<String, Employee> topEmployeesByDept = employeeList.stream()
    .collect(Collectors.groupingBy(
        Employee::getDepartment,
        Collectors.collectingAndThen(Collectors.toList(),
            list -> list.stream()
                .sorted(Comparator.comparing(Employee::getSalary))
                .skip(1).findFirst().orElseThrow())
    ));

Note that although this approach is relatively simple, it's definitely not the most performant one.

This solution has a linear-logarithmic time complexity O(n log n), meanwhile it can be done with almost linear time complexity O(1) because this task is very close to searching an employee having the highest salary.

Also, the solution provided above doesn't tackle the case when several Employees have the salary equal to the highest salary in their department. In this case skip(1) would not work - it would an employee having the highest salary in the department (not the second highest). To avoid this issue we can use an auxiliary map to associate only one employee with a particular salary within its department.

In order to an employee having the second-highest salary in a department, we can maintain a PriorityQueue of size 2, which would contain two Employee objects with the highest salaries encountered so far.

That's how it might be implemented:

List<Employee> employeeList = List.of();
        
Map<String, Employee> topEmployeesByDept = employeeList.stream()
    .collect(Collectors.groupingBy(
        Employee::getDepartment,
        Collectors.toMap(
            Employee::getSalary,
            Function.identity(),
            (left, right) -> left
        )
    ))
    .entrySet().stream()
    .collect(Collectors.toMap(
        Map.Entry::getKey,
        entry -> entry.getValue().values().stream()
            .collect(Collector.of(
                () -> new PriorityQueue<>(Comparator.comparing(Employee::getSalary)),
                (Queue<Employee> queue, Employee next) -> tryAdd(queue, next),
                (Queue<Employee> left, Queue<Employee> right) -> {
                    right.forEach(next -> tryAdd(left, next));
                    return left;
                },
                Queue::remove
            ))
    ));

public static void tryAdd(Queue<Employee> queue, Employee next) {
    if (queue.size() == 2 && queue.element().getSalary() < next.getSalary()) queue.remove(); // if next value is greater than the smallest element in the queue and max size has been exceeded the smallest element needs to be removed from the queue
    if (queue.size() < 2) queue.add(next);
}
Alexander Ivanchenko0
Related