Department Top Three Salaries - Solution & Explanation

Problem Overview: You are given employee salary records and department information. The task is to return employees whose salary ranks in the top three distinct salaries within their department. Multiple employees can share the same salary, so ranking must behave like DENSE_RANK rather than a simple top-three list.

Approach 1: SQL-like Grouping and Filtering (O(n log n) time, O(n) space)

This method mirrors how you would solve the problem in SQL using GROUP BY and ranking. First, group employees by department using a dictionary or map. Inside each group, collect the distinct salary values and sort them in descending order. The third highest distinct salary becomes the threshold for that department. Finally, iterate through the employees again and select those whose salary is greater than or equal to this threshold.

The key insight is separating salary ranking from employee filtering. You compute the top three distinct salaries first, then match employees against that set. Sorting each department’s salaries dominates the runtime, resulting in O(n log n) time overall with O(n) extra space for grouped data. This approach closely reflects database logic and is easy to implement in Python or JavaScript using maps and arrays. It heavily relies on concepts similar to hash maps and database grouping.

Approach 2: Using Data Structures and Sorting (O(n log n) time, O(n) space)

Another practical solution groups employees by department and sorts employees within each department by salary in descending order. While scanning the sorted list, track the number of distinct salary levels encountered. Each time the salary value changes, increase the rank counter. Continue collecting employees until the rank exceeds three.

This approach avoids building a separate salary set because the sorting order naturally exposes salary ranks. A simple loop maintains the current rank and ensures employees tied with the same salary share the same position. Sorting each department’s employee list drives the complexity to O(n log n) time with O(n) space for grouping. It’s straightforward to implement in Java using collections and comparators and relies on standard sorting techniques.

Recommended for interviews: The grouping plus ranking approach is what most interviewers expect. It shows you understand how to partition data by department and handle duplicate salaries correctly using dense ranking. A brute-force scan of every employee against all others demonstrates the idea but scales poorly. The grouped sorting or SQL-style ranking solution clearly communicates both algorithmic thinking and familiarity with real-world database queries.