Watch 2 video solutions for Second Highest Salary II, a medium level problem involving Database. This walkthrough by Everyday Data Science has 647 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Table: employees
+------------------+---------+ | Column Name | Type | +------------------+---------+ | emp_id | int | | salary | int | | dept | varchar | +------------------+---------+ emp_id is the unique key for this table. Each row of this table contains information about an employee including their ID, salary, and department.
Write a solution to find the employees who earn the second-highest salary in each department. If multiple employees have the second-highest salary, include all employees with that salary.
Return the result table ordered by emp_id in ascending order.
The result format is in the following example.
Example:
Input:
employees table:
+--------+--------+-----------+ | emp_id | salary | dept | +--------+--------+-----------+ | 1 | 70000 | Sales | | 2 | 80000 | Sales | | 3 | 80000 | Sales | | 4 | 90000 | Sales | | 5 | 55000 | IT | | 6 | 65000 | IT | | 7 | 65000 | IT | | 8 | 50000 | Marketing | | 9 | 55000 | Marketing | | 10 | 55000 | HR | +--------+--------+-----------+
Output:
+--------+-----------+ | emp_id | dept | +--------+-----------+ | 2 | Sales | | 3 | Sales | | 5 | IT | | 8 | Marketing | +--------+-----------+
Explanation:
Problem Overview: You need to return the second highest distinct salary from a database table. If a second highest value does not exist, the query should return NULL. The challenge is handling duplicates correctly while keeping the query concise and efficient.
Approach 1: Subquery with ORDER BY and OFFSET (O(n log n) time, O(1) extra space)
One direct approach is sorting distinct salaries in descending order and selecting the second entry. In MySQL, this is done using SELECT DISTINCT salary FROM Employee ORDER BY salary DESC LIMIT 1 OFFSET 1. The database engine sorts all unique salaries, then skips the first (highest) value. Sorting dominates the cost, giving O(n log n) time. This approach works well for quick queries but can feel brittle if the schema evolves or additional ranking logic is needed.
Approach 2: Window Function with DENSE_RANK (O(n log n) time, O(n) space)
Window functions provide a cleaner and more scalable solution. Use DENSE_RANK() over salaries ordered descending to assign ranks where equal salaries share the same rank. The highest salary receives rank 1, the second distinct salary receives rank 2. After computing ranks, filter rows where rank = 2. This method naturally handles duplicates and is widely supported in modern SQL engines. The ranking operation internally requires sorting, leading to O(n log n) time and O(n) intermediate space.
Example pattern:
SELECT salary FROM (SELECT salary, DENSE_RANK() OVER (ORDER BY salary DESC) r FROM Employee) t WHERE r = 2;
This approach is common in analytics queries and translates well to data processing tools like pandas. It also builds intuition for solving ranking problems with SQL window functions such as DENSE_RANK, RANK, and ROW_NUMBER.
Recommended for interviews: The window function approach using DENSE_RANK() is typically expected. It demonstrates strong SQL fundamentals and shows you understand how to handle duplicates with ranking semantics. The simple subquery approach proves you understand ordering and filtering, but the window function solution signals deeper knowledge of modern SQL patterns used in production data systems.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Subquery with DISTINCT + ORDER BY + OFFSET | O(n log n) | O(1) | Quick solution when the database supports LIMIT/OFFSET and the dataset is moderate. |
| Window Function (DENSE_RANK) | O(n log n) | O(n) | Preferred modern SQL approach. Handles duplicates cleanly and scales well for ranking problems. |
