Skip to main content
Talentd

Nth Highest Salary - Solution & Explanation

MediumDatabase11 min readAsked at: Amazon, Microsoft, Meta +8
Practice this problem

Problem Statement

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                   |
+------------------------+

Approach Overview

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 1: Use SQL Query with LIMIT and OFFSET for Nth Highest Salary

This approach uses the SQL query constructs to fetch the nth highest salary directly from the database. We will utilize ORDER BY, DISTINCT, LIMIT, and OFFSET to achieve this.

Steps:

  • First, eliminate duplicate salaries using SELECT DISTINCT.
  • Sort the result in descending order using ORDER BY salary DESC.
  • Use LIMIT and OFFSET to skip the first n-1 results and take the nth result if it exists.

This function is a stub that generates an SQL query string. The actual execution with parameters would be performed using an SQL interface in C like SQLite or MySQL Connector C API.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

  • Time Complexity: O(n), where n is the number of unique salaries.
  • Space Complexity: O(1) for the SQL query execution by the database engine.
Try this approach in the editor →

Approach 2: Use Subquery with DENSE_RANK to Identify Nth Highest Salary

In this approach, we will use the DENSE_RANK() window function available in SQL to assign ranks to salaries based on their value.

Steps:

  • Rank salaries using DENSE_RANK by partitioning properly.
  • Select the salary where the rank matches the input n.
  • This accounts for duplicate values effectively while ranking.

This function generates an SQL query string that uses the DENSE_RANK function to assign ranks and filter out the nth highest salary.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

  • Time Complexity: O(n) - Rankings need to be computed over all distinct salary entries.
  • Space Complexity: O(1)
Try this approach in the editor →

Approach 3: Default Approach

Code

PythonMySQL

Python

MySQL

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Use SQL Query with LIMIT and OFFSET for Nth Highest Salary
  • Time Complexity: O(n), where n is the number of unique salaries.
  • Space Complexity: O(1) for the SQL query execution by the database engine.
Use Subquery with DENSE_RANK to Identify Nth Highest Salary
  • Time Complexity: O(n) - Rankings need to be computed over all distinct salary entries.
  • Space Complexity: O(1)
Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
ORDER BY with LIMIT and OFFSETO(n log n)O(1)When you only need the Nth value after sorting and want a concise query
Subquery with DENSE_RANK Window FunctionO(n log n)O(n)When duplicate values must share the same rank or when writing analytical SQL queries

Video Solution

LeetCode 177: Nth Highest Salary [SQL] • Frederik Müller • 27,253 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Nth Highest Salary easy or hard?
Nth Highest Salary is considered a medium difficulty SQL problem. The challenge comes from handling duplicate salaries correctly and understanding ranking techniques like DISTINCT sorting or window functions.
Nth Highest Salary Python/Java solution
When solved outside SQL, languages like Python or Java typically store salaries in an array or list, remove duplicates using a set, sort in descending order, and return the Nth element. The complexity is O(n log n) due to sorting.
How to solve Nth Highest Salary in O(n)?
Pure O(n) solutions are uncommon in SQL because ranking usually requires sorting. Database engines rely on ORDER BY or window functions that internally perform O(n log n) sorting. Achieving true O(n) would require specialized indexing or precomputed ranking structures.
What is the best approach for Nth Highest Salary?
The most robust approach uses the SQL window function DENSE_RANK(). It ranks salaries in descending order and selects rows where the rank equals N. This correctly handles duplicate salaries because identical values share the same rank.
Is Nth Highest Salary asked at Google/Amazon/Meta?
Nth Highest Salary is a common SQL interview problem across companies like Amazon, Google, Meta, and Microsoft. It tests knowledge of ranking queries, DISTINCT handling, and SQL window functions such as DENSE_RANK or ROW_NUMBER.
What data structure is used in Nth Highest Salary?
The problem is solved using SQL query operations rather than traditional data structures. Internally, the database relies on sorting algorithms and ranking mechanisms like DENSE_RANK, often backed by indexes or temporary sorted structures.
What is the time complexity of Nth Highest Salary?
Most SQL solutions require sorting the salary column, which takes O(n log n) time. Window functions like DENSE_RANK() also depend on sorting internally, so they have the same overall complexity. Space complexity ranges from O(1) to O(n) depending on the query plan.

Ready to solve this problem?

Practice Nth Highest Salary with our built-in code editor and test cases.

Practice on FleetCode
Previous

The Number of Users That Are Eligible for Discount