Watch 10 video solutions for Nth Highest Salary, a medium level problem involving Database. This walkthrough by Gate Smashers has 622,466 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Table: Employee
+-------------+------+ | Column Name | Type | +-------------+------+ | id | int | | salary | int | +-------------+------+ id is the primary key (column with unique values) for this table. Each row of this table contains information about the salary of an employee.
Write a solution to find the nth highest salary from the Employee table. If there is no nth highest salary, return null.
The result format is in the following example.
Example 1:
Input: Employee table: +----+--------+ | id | salary | +----+--------+ | 1 | 100 | | 2 | 200 | | 3 | 300 | +----+--------+ n = 2 Output: +------------------------+ | getNthHighestSalary(2) | +------------------------+ | 200 | +------------------------+
Example 2:
Input: Employee table: +----+--------+ | id | salary | +----+--------+ | 1 | 100 | +----+--------+ n = 2 Output: +------------------------+ | getNthHighestSalary(2) | +------------------------+ | null | +------------------------+
Problem Overview: Given an Employee table containing salaries, return the Nth highest distinct salary. If the table does not contain N unique salaries, the query should return NULL. The main challenge is handling duplicate salaries while correctly identifying the Nth rank.
Approach 1: ORDER BY with LIMIT and OFFSET (Time: O(n log n), Space: O(1))
This approach sorts all salaries in descending order and skips the first N-1 distinct entries using LIMIT and OFFSET. The query typically wraps the ordered results inside a subquery and selects the Nth row. Sorting dominates the cost, giving O(n log n) time complexity, while the query itself uses constant extra space.
The key detail is ensuring duplicate salaries don't affect ranking. This is usually handled with DISTINCT before applying the sort. The database engine performs the sort operation, then offsets rows until it reaches the desired position. This solution is concise and works well when you simply need the Nth value from a sorted dataset.
Problems like this commonly appear in SQL and database interview rounds because they test understanding of sorting, filtering, and result pagination.
Approach 2: Subquery with DENSE_RANK Window Function (Time: O(n log n), Space: O(n))
This method assigns a rank to each salary using the DENSE_RANK() window function ordered by salary descending. Employees with the same salary receive the same rank, which naturally handles duplicates. After ranking, a subquery filters rows where rank = N.
The database first sorts salaries to compute the window function, which takes O(n log n) time. Storing ranking metadata requires additional memory, leading to O(n) space. Despite this overhead, the logic is clearer and explicitly models the ranking problem.
Window functions are heavily used in analytical queries and appear frequently in advanced SQL window function problems. This approach scales well when additional ranking logic or grouped analytics are required.
Recommended for interviews: Both solutions are valid, but interviewers often prefer the DENSE_RANK() solution because it demonstrates strong knowledge of SQL window functions and ranking semantics. The LIMIT/OFFSET approach shows you understand sorting and pagination, but the ranking-based solution better handles duplicates and mirrors how real analytical queries are written.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| ORDER BY with LIMIT and OFFSET | O(n log n) | O(1) | When you only need the Nth value after sorting and want a concise query |
| Subquery with DENSE_RANK Window Function | O(n log n) | O(n) | When duplicate values must share the same rank or when writing analytical SQL queries |
