# 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 `n`th highest distinct salary.

If there are fewer than `n` distinct salaries, the function should return `null`. The official problem asks for the `n`th 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:

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

## Examples

Example 1:

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

N = 2
```

The distinct salaries in descending order are:

```text
300, 200, 100
```

The second highest salary is `200`.

Output:

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

Example 2:

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

N = 2
```

There is only one distinct salary.

So the second highest salary does not exist.

Output:

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

## First Thought: Sort Distinct Salaries

The most direct idea is:

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

For example, if salaries are:

```text
300, 200, 100
```

and `N = 2`, then we skip `1` salary:

```text
300
```

The next salary is:

```text
200
```

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:

```sql
N - 1
```

as the offset.

## Algorithm

Inside the SQL function:

1. Convert `N` into an offset by subtracting `1`.
2. Select distinct salaries.
3. Sort them in descending order.
4. Skip `N - 1` rows.
5. 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 `N`th 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

```sql
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:

```sql
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:

```sql
SELECT DISTINCT salary
FROM Employee
ORDER BY salary DESC
```

`DISTINCT` removes duplicates.

`ORDER BY salary DESC` puts the highest salaries first.

Finally:

```sql
LIMIT 1 OFFSET N
```

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

For example, original `N = 2`.

After subtraction:

```sql
N = 1
```

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

## Testing

Test case 1:

```sql
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:

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

Test case 2:

```sql
DELETE FROM Employee;

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

SELECT getNthHighestSalary(2);
```

Expected:

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

Test case 3:

```sql
DELETE FROM Employee;

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

SELECT getNthHighestSalary(2);
```

Distinct salaries:

```text
300, 200, 100
```

Expected:

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

Test case 4:

```sql
DELETE FROM Employee;

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

SELECT getNthHighestSalary(1);
```

Expected:

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