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.

Description Solution Video 6:40

177. Nth Highest Salary

Medium40.5% acceptance11 companies

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 n^th highest salary from the Employee table. If there is no n^th 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                   |
+------------------------+