LeetCode 177: Nth Highest Salary

Problem Restatement

We are given a table named Employee.

Column	Type
id	int
salary	int

Each row stores one employee and that employee’s salary.

We need to write a SQL function that returns the nth highest distinct salary.

If there are fewer than n distinct salaries, the function should return null. The official problem asks for the nth highest distinct salary from Employee, returning null when fewer than n distinct salaries exist.

Input and Output

Item	Meaning
Input	Table `Employee(id, salary)` and integer `N`
Output	The `N`th highest distinct salary
Function name	`getNthHighestSalary(N)`
Missing value case	Return `null`

Example function shape:

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
    ...
END

Examples

Example 1:

Employee
+----+--------+
| id | salary |
+----+--------+
| 1  | 100    |
| 2  | 200    |
| 3  | 300    |
+----+--------+

N = 2

The distinct salaries in descending order are:

300, 200, 100

The second highest salary is 200.

Output:

+------------------------+
| getNthHighestSalary(2) |
+------------------------+
| 200                    |
+------------------------+

Example 2:

Employee
+----+--------+
| id | salary |
+----+--------+
| 1  | 100    |
+----+--------+

N = 2

There is only one distinct salary.

So the second highest salary does not exist.

Output:

+------------------------+
| getNthHighestSalary(2) |
+------------------------+
| null                   |
+------------------------+

First Thought: Sort Distinct Salaries

The most direct idea is:

Get all distinct salaries.
Sort them from highest to lowest.
Skip the first N - 1 salaries.
Return the next salary.

For example, if salaries are:

300, 200, 100

and N = 2, then we skip 1 salary:

The next salary is:

So the answer is 200.

Key Insight

SQL already has the tools needed for this problem:

SQL feature	Role
`DISTINCT`	Removes duplicate salary values
`ORDER BY salary DESC`	Sorts salaries from highest to lowest
`LIMIT 1`	Takes one salary
`OFFSET N - 1`	Skips the first `N - 1` salary levels

The important detail is that OFFSET needs a zero-based index.

So:

N	Meaning	OFFSET
1	highest salary	0
2	second highest salary	1
3	third highest salary	2

Therefore, we use:

N - 1

as the offset.

Algorithm

Inside the SQL function:

Convert N into an offset by subtracting 1.
Select distinct salaries.
Sort them in descending order.
Skip N - 1 rows.
Return one row.

Correctness

After DISTINCT, each salary level appears once.

After ORDER BY salary DESC, the salary levels are arranged from highest to lowest.

The salary at offset 0 is the highest salary.

The salary at offset 1 is the second highest salary.

In general, the salary at offset N - 1 is the Nth highest distinct salary.

So returning the row at OFFSET N - 1 gives the correct answer.

If there are fewer than N distinct salaries, then the query has no row at that offset. In a scalar return context, this produces null, which matches the required result.

Complexity

Metric	Value	Why
Time	`O(n log n)`	The database may sort distinct salary values
Space	`O(n)`	The database may store distinct salary values during sorting

With an index on salary, the database engine may execute this more efficiently.

Implementation

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
    SET N = N - 1;

    RETURN (
        SELECT DISTINCT salary
        FROM Employee
        ORDER BY salary DESC
        LIMIT 1 OFFSET N
    );
END

Code Explanation

This line converts the rank into an offset:

SET N = N - 1;

If we want the first highest salary, we need offset 0.

If we want the second highest salary, we need offset 1.

Then this query builds the ordered salary list:

SELECT DISTINCT salary
FROM Employee
ORDER BY salary DESC

DISTINCT removes duplicates.

ORDER BY salary DESC puts the highest salaries first.

Finally:

LIMIT 1 OFFSET N

skips the first N rows after the earlier subtraction, then returns one salary.

For example, original N = 2.

After subtraction:

N = 1

Then OFFSET 1 skips the highest salary and returns the next salary.

Testing

Test case 1:

CREATE TABLE Employee (
    id INT PRIMARY KEY,
    salary INT
);

INSERT INTO Employee (id, salary) VALUES
(1, 100),
(2, 200),
(3, 300);

SELECT getNthHighestSalary(2);

Expected:

+------------------------+
| getNthHighestSalary(2) |
+------------------------+
| 200                    |
+------------------------+

Test case 2:

DELETE FROM Employee;

INSERT INTO Employee (id, salary) VALUES
(1, 100);

SELECT getNthHighestSalary(2);

Expected:

+------------------------+
| getNthHighestSalary(2) |
+------------------------+
| null                   |
+------------------------+

Test case 3:

DELETE FROM Employee;

INSERT INTO Employee (id, salary) VALUES
(1, 100),
(2, 100),
(3, 200),
(4, 300),
(5, 300);

SELECT getNthHighestSalary(2);

Distinct salaries:

300, 200, 100

Expected:

+------------------------+
| getNthHighestSalary(2) |
+------------------------+
| 200                    |
+------------------------+

Test case 4:

DELETE FROM Employee;

INSERT INTO Employee (id, salary) VALUES
(1, 100),
(2, 200),
(3, 300);

SELECT getNthHighestSalary(1);

Expected:

+------------------------+
| getNthHighestSalary(1) |
+------------------------+
| 300                    |
+------------------------+