Skip to content

LeetCode 176 - Second Highest Salary

Database Language: PostgreSQL

Difficulty: ⭐⭐⭐

Problem Description

Input

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.

Requirement

Write a solution to find the second highest salary from the Employee table. If there is no second highest salary, return null (return None in Pandas).

The result format is in the following example.

Examples

Example 1

Input

Employee table:

id salary
1 100
2 200
3 300
Output
SecondHighestSalary
200

Example 2

Input

Employee table:

id salary
1 100
Output
SecondHighestSalary
NULL

SQL Schema

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

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

Solutions

Solution #1 - Using LIMIT ... OFFSET

Based on the requirement of finding the second highest salary, one of the first things that may come into mind is the LIMIT ... OFFSET clause of the SELECT statement.

SELECT DISTINCT salary AS SecondHighestSalary
FROM Employee
ORDER BY salary DESC
LIMIT 1 OFFSET 1;

What this query does is to select all the distinct salary from the Employee table (SELECT DISTINCT salary FROM Employee), then sort the salary in descending order (ORDER BY salary DESC), then return just 1 row (LIMIT 1) but skipping the first row (OFFSET 1).

This query will return the second highest salary if there is more than 1 unique salary in the Employee table. But if there is only 1 unique salary in the Employee table, this query will return an empty set instead of a NULL value, which is what the question requires. To overcome this issue, a NULL salary can be included in the list of salaries using the UNION ALL statement:

SELECT DISTINCT salary FROM Employee
UNION ALL
SELECT NULL AS salary

Now that a second-highest salary will always exist, the original query above can be modified as follows:

# Final Solution 1 Query - Using LIMIT ... OFFSET
SELECT salary AS SecondHighestSalary
FROM (SELECT DISTINCT salary FROM Employee UNION ALL SELECT NULL AS salary) emp_salaries
ORDER BY salary DESC NULLS LAST
LIMIT 1 OFFSET 1;

Take note of the NULLS LAST option in the ORDER BY salary. The NULLS FIRST and NULLS LAST options can be used to determine whether nulls appear before or after non-null values in the sort ordering. By default, null values sort as if larger than any non-null value; that is, NULLS FIRST is the default for DESC order, and NULLS LAST otherwise.

The fastest run-time for this query is as follows:

  • Runtime: 194ms
  • Beats: 91.18% as of July 15, 2024

Another way of writing the query is with the use of a common-table expression (CTE) wherein the list of unique salaries are created as a CTE and referenced in the main SELECT statement:

# Final Solution 1 Query - Using LIMIT ... OFFSET and CTE
WITH emp_salaries AS (
    SELECT DISTINCT salary FROM Employee
    UNION ALL
    SELECT NULL AS salary
)
SELECT salary AS SecondHighestSalary
FROM emp_salaries
ORDER BY salary DESC NULLS LAST
LIMIT 1 OFFSET 1;

The fastest run-time for this updated query that uses a common-table expression (CTE) is as follows:

  • Runtime: 195ms
  • Beats: 90.15% as of July 15, 2024

Although the fastest runtime that uses the common-table expression (CTE) was slower than the previous query that does not use a CTE, the generated query plan for both queries are the same, which is as follows:

Limit  (cost=43.28..43.28 rows=1 width=4)
  ->  Sort  (cost=43.27..43.78 rows=201 width=4)
        Sort Key: employee.salary DESC NULLS LAST
        ->  Append  (cost=38.25..41.27 rows=201 width=4)
              ->  HashAggregate  (cost=38.25..40.25 rows=200 width=4)
                    Group Key: employee.salary
                    ->  Seq Scan on employee  (cost=0.00..32.60 rows=2260 width=4)
              ->  Result  (cost=0.00..0.01 rows=1 width=4)

Solution #2 - Using RANK. DENSE_RANK or ROW_NUMBER Window Function

Another way of finding the second highest salary is with the use of RANK, DENSE_RANK or even the ROW_NUMBER window functions. If the salary values being "ranked" are all unique, then the output of the RANK, DENSE_RANK and ROW_NUMBER window functions will be the same.

Just like the case in the first solution, the first step is to get all the unique salaries from the Employee table:

SELECT DISTINCT salary FROM Employee

The next step is to rank these salaries from highest to lowest:

SELECT salary, DENSE_RANK() OVER (ORDER BY salary DESC NULLS LAST) as ranking
FROM (SELECT DISTINCT salary FROM Employee) emp_salaries

Just like in the first solution, take note of the NULLS LAST option in the ORDER BY salary. The NULLS FIRST and NULLS LAST options can be used to determine whether nulls appear before or after non-null values in the sort ordering. By default, null values sort as if larger than any non-null value; that is, NULLS FIRST is the default for DESC order, and NULLS LAST otherwise.

Last step is to return the second highest salary:

SELECT salary AS SecondHighestSalary
FROM (SELECT salary, DENSE_RANK() OVER (ORDER BY salary DESC NULLS LAST) as ranking
      FROM (SELECT DISTINCT salary FROM Employee) emp_salaries) salary_ranking
WHERE ranking = 2;

Just like the issue in the first solution, if there is only 1 unique salary in the Employee table, this query will return an empty set instead of a NULL value, which is the required output. To overcome this issue, a NULL salary can be included in the list of salaries using the UNION ALL statement:

# Final Solution 2 Query - Using DENSE_RANK Window Function
SELECT salary AS SecondHighestSalary
FROM (SELECT salary, DENSE_RANK() OVER (ORDER BY salary DESC NULLS LAST) as ranking
      FROM (SELECT DISTINCT salary FROM Employee UNION ALL SELECT NULL AS salary) emp_salaries) salary_ranking
WHERE ranking = 2;

This query can be re-written using common-table expressions (CTEs), one for each of the sub-queries:

# Final Solution 2 Query - Using DENSE_RANK Window Function and CTE
WITH emp_salaries AS (
    SELECT DISTINCT salary FROM Employee
    UNION ALL
    SELECT NULL AS salary
),
salary_ranking AS (
    SELECT salary, DENSE_RANK() OVER (ORDER BY salary DESC NULLS LAST) AS ranking
    FROM emp_salaries
)
SELECT salary AS SecondHighestSalary
FROM salary_ranking
WHERE ranking = 2

As mentioned earlier, if the salaries being "ranked" are all unique, which is the case here since only the DISTINCT salary is being ranked, then the DENSE_RANK in the query can be replaced by either the RANK or ROW_NUMBER window function and the result will be the same.

Here's the query plan generated by PostgreSQL for both of the queries above for the second solution:

Subquery Scan on salary_ranking  (cost=48.95..54.98 rows=1 width=4)
  Filter: (salary_ranking.ranking = 2)
  ->  WindowAgg  (cost=48.95..52.47 rows=201 width=12)
        Run Condition: (dense_rank() OVER (?) <= 2)
        ->  Sort  (cost=48.95..49.46 rows=201 width=4)
              Sort Key: employee.salary DESC NULLS LAST
              ->  Append  (cost=38.25..41.27 rows=201 width=4)
                    ->  HashAggregate  (cost=38.25..40.25 rows=200 width=4)
                          Group Key: employee.salary
                          ->  Seq Scan on employee  (cost=0.00..32.60 rows=2260 width=4)
                    ->  Result  (cost=0.00..0.01 rows=1 width=4)
  • Runtime: 193ms
  • Beats: 92.28% as of July 15, 2024

Solution #3 - Using MAX Aggregate Function and Subquery

There is yet a third way of getting the second highest salary from the Employee table without the use of a window function such as RANK, DENSE_RANK or ROW_NUMBER and without the use of the LIMIT ... OFFSET clause of the SELECT statement.

Another way of looking at the question is, what is the highest salary that is less than the highest salary. The highest salary from the Employee table can be derived by the following query:

SELECT MAX(salary) FROM Employee

This query just needs to be plugged into another query that will get the highest salary that is less than the output of this query and that query will look as follows:

# Final Solution 3 Query - Using MAX Aggregate Function and Subquery
SELECT MAX(salary) AS SecondHighestSalary
FROM Employee
WHERE Employee.salary < (SELECT MAX(salary) FROM Employee)

If there is no salary that is less than the highest salary, then this query will return a NULL value and not an empty set. The advantage of this solution is that it does not need to use a common-table expression (CTE) and it doesn't need to "insert" a NULL value to the list of salaries to overcome the issue of having only 1 unique salary.

Here's the query plan for this query:

Aggregate  (cost=78.39..78.40 rows=1 width=4)
  InitPlan 1 (returns $0)
    ->  Aggregate  (cost=38.25..38.26 rows=1 width=4)
          ->  Seq Scan on employee employee_1  (cost=0.00..32.60 rows=2260 width=4)
  ->  Seq Scan on employee  (cost=0.00..38.25 rows=753 width=4)
        Filter: (salary < $0)
  • Runtime: 186ms
  • Beats: 99.25% as of July 15, 2024

Solution Runtime Comparison

Here's the comparison of the fastest runtime for each of the solutions.

Solution # Runtime Beats
1a - Using LIMIT ... OFFSET 194ms 91.18%
1b - Using LIMIT ... OFFSET and CTE 195ms 90.15%
2 - Using RANK. DENSE_RANK or ROW_NUMBER Window Function 193ms 92.28%
3 - Using MAX Aggregate Function and Subquery 186ms 99.25%