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:

SecondHighestSalary

Examples

Example 1:

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

The distinct salaries are:

300, 200, 100

The second highest salary is 200.

Output:

+---------------------+
| SecondHighestSalary |
+---------------------+
| 200                 |
+---------------------+

Example 2:

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

There is only one distinct salary.

So there is no second highest salary.

Output:

+---------------------+
| SecondHighestSalary |
+---------------------+
| null                |
+---------------------+

First Thought: Sort Distinct Salaries

A natural way is:

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

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

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.

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:

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

This avoids sorting explicitly.

Algorithm

First, find the highest salary:

SELECT MAX(salary)
FROM Employee

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

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:

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

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

Code Explanation

The inner query:

SELECT MAX(salary)
FROM Employee

finds the highest salary in the whole table.

The WHERE clause:

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

removes every row with the highest salary.

The outer query:

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:

100, 200, 300, 300

The highest salary is 300.

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

100, 200

The maximum remaining salary is 200.

Alternative Implementation

This version follows the sorting idea directly:

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:

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:

+---------------------+
| SecondHighestSalary |
+---------------------+
| 200                 |
+---------------------+

Test case 2:

DELETE FROM Employee;

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

Expected:

+---------------------+
| SecondHighestSalary |
+---------------------+
| null                |
+---------------------+

Test case 3:

DELETE FROM Employee;

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

Expected:

+---------------------+
| SecondHighestSalary |
+---------------------+
| null                |
+---------------------+

Test case 4:

DELETE FROM Employee;

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

Expected:

+---------------------+
| SecondHighestSalary |
+---------------------+
| 200                 |
+---------------------+