# LeetCode 176: Second Highest Salary

## Problem Restatement

We are given a table named `Employee`.

| Column | Type |
|---|---|
| id | int |
| salary | int |

Each row stores one employee and their salary.

We need to return the second highest distinct salary.

The word distinct matters. If two employees both have salary `300`, that salary still counts as one salary level.

If there is no second highest distinct salary, we return `null`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Table `Employee(id, salary)` |
| Output | One column named `SecondHighestSalary` |
| Rule | Return the second highest distinct salary |
| Empty result case | Return `null` |

Expected output column:

```sql
SecondHighestSalary
```

## Examples

Example 1:

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

The distinct salaries are:

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

The second highest salary is `200`.

Output:

```text
+---------------------+
| SecondHighestSalary |
+---------------------+
| 200                 |
+---------------------+
```

Example 2:

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

There is only one distinct salary.

So there is no second highest salary.

Output:

```text
+---------------------+
| SecondHighestSalary |
+---------------------+
| null                |
+---------------------+
```

## First Thought: Sort Distinct Salaries

A natural way is:

1. Select all distinct salaries.
2. Sort them from highest to lowest.
3. Skip the first one.
4. Take the next one.

In MySQL, this can be written with `DISTINCT`, `ORDER BY`, `LIMIT`, and `OFFSET`.

```sql
SELECT DISTINCT salary
FROM Employee
ORDER BY salary DESC
LIMIT 1 OFFSET 1;
```

This gives the second highest distinct salary.

But there is a problem.

If there is no second highest salary, this query returns no row. LeetCode expects one row with `null`.

So we wrap it inside another `SELECT`.

```sql
SELECT (
    SELECT DISTINCT salary
    FROM Employee
    ORDER BY salary DESC
    LIMIT 1 OFFSET 1
) AS SecondHighestSalary;
```

A scalar subquery that finds nothing becomes `null`, which matches the required output.

## Key Insight

The second highest salary is the largest salary that is strictly smaller than the highest salary.

So we can say:

```text
second highest = MAX(salary) among salaries less than MAX(salary)
```

This avoids sorting explicitly.

## Algorithm

First, find the highest salary:

```sql
SELECT MAX(salary)
FROM Employee
```

Then keep only rows whose salary is smaller than that maximum:

```sql
WHERE salary < (
    SELECT MAX(salary)
    FROM Employee
)
```

Finally, among those remaining rows, take the maximum salary.

That maximum is the second highest distinct salary.

## Correctness

Let the highest salary in the table be `H`.

Any second highest distinct salary must be smaller than `H`.

So we filter the table to salaries where:

```sql
salary < H
```

After this filter, all rows with the highest salary are removed.

Among the remaining salaries, the largest value is exactly the second highest distinct salary.

If no salary remains after the filter, then the table has fewer than two distinct salary values. In that case, `MAX(...)` over an empty set returns `null`, which is the expected answer.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | The table may be scanned to compute the maximum values |
| Space | `O(1)` | Only aggregate values are needed |

With an index on `salary`, the database may optimize this further, but the logical complexity is linear.

## Implementation

```sql
SELECT
    MAX(salary) AS SecondHighestSalary
FROM Employee
WHERE salary < (
    SELECT MAX(salary)
    FROM Employee
);
```

## Code Explanation

The inner query:

```sql
SELECT MAX(salary)
FROM Employee
```

finds the highest salary in the whole table.

The `WHERE` clause:

```sql
WHERE salary < (
    SELECT MAX(salary)
    FROM Employee
)
```

removes every row with the highest salary.

The outer query:

```sql
SELECT MAX(salary) AS SecondHighestSalary
```

then finds the largest salary among the remaining rows.

That value is the second highest distinct salary.

This handles duplicates naturally. For example:

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

The highest salary is `300`.

After filtering out salaries equal to `300`, the remaining salaries are:

```text
100, 200
```

The maximum remaining salary is `200`.

## Alternative Implementation

This version follows the sorting idea directly:

```sql
SELECT (
    SELECT DISTINCT salary
    FROM Employee
    ORDER BY salary DESC
    LIMIT 1 OFFSET 1
) AS SecondHighestSalary;
```

It is easy to read, but it depends on `LIMIT OFFSET`, which is MySQL style.

The `MAX` version is usually cleaner for this exact problem.

## 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
    MAX(salary) AS SecondHighestSalary
FROM Employee
WHERE salary < (
    SELECT MAX(salary)
    FROM Employee
);
```

Expected:

```text
+---------------------+
| SecondHighestSalary |
+---------------------+
| 200                 |
+---------------------+
```

Test case 2:

```sql
DELETE FROM Employee;

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

Expected:

```text
+---------------------+
| SecondHighestSalary |
+---------------------+
| null                |
+---------------------+
```

Test case 3:

```sql
DELETE FROM Employee;

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

Expected:

```text
+---------------------+
| SecondHighestSalary |
+---------------------+
| null                |
+---------------------+
```

Test case 4:

```sql
DELETE FROM Employee;

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

Expected:

```text
+---------------------+
| SecondHighestSalary |
+---------------------+
| 200                 |
+---------------------+
```