Nth Highest Salary | LeetCode | MSSQL

Problem Statement

In this post, we'll be addressing a common SQL problem: finding the nth highest salary from a table of employees. If there is no nth highest salary, the query should return null. This type of problem often shows up in coding assessments and job interviews, so let's delve into the solution. The structure of the Employee table is as follows:

The id is the primary key, and each row contains salary information for an employee.

The objective is to write an SQL query that can return the nth highest salary.

Example 1:

With n = 2, the output would be:

Example 2:

With n = 2, the output would be:

Approaches to the Solution

We'll explore two approaches that involve creating a SQL function to solve the problem. Each method uses different concepts and techniques in SQL. We'll explain each one and highlight their strengths and weaknesses.

1. Using a Stored Function with DENSE_RANK()

The first solution creates a stored function getNthHighestSalary which uses the DENSE_RANK() window function to rank the salaries in descending order.

CREATE FUNCTION getNthHighestSalary(@N INT) RETURNS INT AS
BEGIN
    RETURN (
        SELECT s.salary
        FROM
        (
            SELECT DISTINCT
                salary,
                DENSE_RANK() OVER (ORDER BY salary DESC) [drank]
            FROM Employee
        ) [s]
        WHERE s.drank = @N
    );
END

This approach provides a clear and logical solution. However, it is not the most performant, with a runtime of 816ms, beating only 29.26% of LeetCode submissions.

2. Using a Stored Function with ROW_NUMBER()

The second solution also creates a stored function, but instead uses the ROW_NUMBER() window function to rank the salaries in descending order.

CREATE FUNCTION getNthHighestSalary(@N INT) RETURNS INT AS
BEGIN
    RETURN (
        SELECT salary
        FROM (
            SELECT salary, ROW_NUMBER() OVER (ORDER BY salary DESC) AS rn
            FROM (
                SELECT DISTINCT salary
                FROM Employee
            ) AS temp
        ) AS ranked_salaries
        WHERE rn = @N
    );
END

This approach performs slightly better, with a runtime of 704ms, beating 55.52% of LeetCode submissions.

Conclusion

These solutions demonstrate how to use stored functions and window functions to solve a common problem in SQL. While the two approaches are similar, using ROW_NUMBER() slightly outperforms DENSE_RANK() on LeetCode.

However, the best solution can vary depending on the RDBMS and the specific dataset. Therefore, it's always a good idea to test different methods in your specific environment.

You can find the original problem at LeetCode.

For more insightful solutions and tech-related content, feel free to connect with me on my Beacons page.

ranggakd - Link in Bio & Creator Tools | Beacons

@ranggakd | center details summary summary Oh hello there I m a an Programmer AI Tech Writer Data Practitioner Statistics Math Addict Open Source Contributor Quantum Computing Enthusiast details center.

beacons.ai