Nth Highest Salary

LeetCode 177 | Difficulty: Medium

Medium

Problem Description

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.

Write a solution to find the n^th highest distinct salary from the Employee table. If there are less than n distinct salaries, return null.

The result format is in the following example.

Example 1:

Input: 
Employee table:
+----+--------+
| id | salary |
+----+--------+
| 1  | 100    |
| 2  | 200    |
| 3  | 300    |
+----+--------+
n = 2
Output: 
+------------------------+
| getNthHighestSalary(2) |
+------------------------+
| 200                    |
+------------------------+

Example 2:

Input: 
Employee table:
+----+--------+
| id | salary |
+----+--------+
| 1  | 100    |
+----+--------+
n = 2
Output: 
+------------------------+
| getNthHighestSalary(2) |
+------------------------+
| null                   |
+------------------------+

Topics: Database

---

Solutions

Solution 1: MS SQL (Best: 504 ms)

Metric	Value
Runtime	504 ms
Memory	N/A
Date	2018-04-12

Solution

CREATE FUNCTION getNthHighestSalary(@N INT) RETURNS INT AS
BEGIN
    RETURN (
        /* Write your T-SQL query statement below. */
        
        
        SELECT DISTINCT T.Salary FROM 
        (
            SELECT DENSE_RANK() OVER (ORDER BY E.Salary DESC) AS Rank,
            Salary
            FROM EMPLOYEE E
        ) T 
        WHERE T.Rank = @N
    );
END

---

Complexity Analysis

Approach	Time	Space
Solution	$O(n)$	$O(1) to O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.