LeetCode 177 - Nth Highest Salary

Difficulty: 🟡 Medium
Topics: Database

Solution

Problem Understanding

This problem asks us to write a SQL function that returns the nth highest distinct salary from the Employee table.

The table contains two columns:

Column	Meaning
`id`	Unique employee identifier
`salary`	Employee salary

The key detail is that the salary must be distinct. Multiple employees may share the same salary, but duplicate salary values should only be counted once when determining rankings.

For example, suppose the salaries are:

100, 200, 200, 300

The distinct salaries are:

300, 200, 100

The second highest distinct salary is 200, not the second row in sorted order.

The problem also requires that if there are fewer than n distinct salaries, the function must return null.

This is important because a naive solution that simply sorts rows and picks the nth row would fail when duplicates exist.

The expected output format is a single column named:

getNthHighestSalary(n)

where n is the input parameter.

Since this is a database problem, the challenge is not about implementing loops or data structures manually, but about correctly using SQL operations such as:

DISTINCT
sorting
LIMIT
OFFSET
subqueries

The most important edge cases are:

Duplicate salaries

Multiple employees can have the same salary, but duplicates should only count once. 2. Fewer than n distinct salaries

The result must be null. 3. A table with only one row

If n > 1, the answer should still be null. 4. Non-consecutive salary values

Rankings are based on order, not numeric gaps. 5. Large datasets

Efficient filtering and sorting become important.

Approaches

Brute Force Approach

A brute force solution would retrieve all salaries, sort them in descending order, manually remove duplicates, and then select the nth value.

Conceptually, the process looks like this:

Fetch every salary from the table.
Sort all salaries descending.
Remove duplicate salary values.
Return the salary at index n - 1.
Return null if that index does not exist.

This approach works because sorting guarantees correct ranking order, and duplicate removal ensures only distinct salaries are counted.

However, this approach is inefficient because it processes more data than necessary. If implemented outside the database engine, it would require transferring all rows into application memory and performing extra work manually.

Optimal Approach

The better solution leverages SQL directly.

The key insight is that SQL already provides operations for:

removing duplicates with DISTINCT
sorting with ORDER BY
selecting a specific ranked row with LIMIT and OFFSET

After removing duplicate salaries and sorting them descending, the nth highest salary is simply the row at position n - 1.

For example:

Distinct salaries descending:
300
200
100

If n = 2, we skip one row (OFFSET 1) and take the next row (LIMIT 1).

If no row exists at that position, SQL automatically returns NULL.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n log n)	O(n)	Sorts all salaries and removes duplicates manually
Optimal	O(n log n)	O(1) or O(n) depending on DB engine	Uses SQL DISTINCT, ORDER BY, LIMIT, and OFFSET

Algorithm Walkthrough

Optimal SQL Algorithm

Select all distinct salary values from the Employee table.

This step is necessary because duplicate salaries should only count once in the ranking. 2. Sort the distinct salaries in descending order.

Descending order places the highest salary first, second highest next, and so on. 3. Skip the first n - 1 rows using OFFSET.

Since indexing starts at zero, the nth highest salary appears after skipping n - 1 entries. 4. Retrieve exactly one row using LIMIT 1.

This ensures only the target salary is returned. 5. Wrap the query inside another SELECT.

This allows the result column to match the required output name:

getNthHighestSalary(n)

If no row exists after the offset, SQL returns NULL.

This naturally handles the edge case where there are fewer than n distinct salaries.

Why it works

The algorithm works because:

DISTINCT guarantees salaries are unique
ORDER BY salary DESC guarantees correct ranking order
OFFSET n - 1 positions the query at the exact rank requested
LIMIT 1 returns only the desired salary

Together, these operations precisely implement the definition of the nth highest distinct salary.

Python Solution

Although this is a SQL problem on LeetCode, the platform expects a MySQL function. Below is the exact LeetCode-submittable SQL solution.

CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT
BEGIN
  RETURN (
      SELECT DISTINCT salary
      FROM Employee
      ORDER BY salary DESC
      LIMIT 1 OFFSET N - 1
  );
END

The function accepts an integer N representing the rank to retrieve.

Inside the function:

SELECT DISTINCT salary removes duplicate salaries
ORDER BY salary DESC sorts salaries from highest to lowest
OFFSET N - 1 skips the first N - 1 salaries
LIMIT 1 retrieves exactly one salary

If the offset goes beyond the available rows, MySQL automatically returns NULL, which satisfies the problem requirements.

Go Solution

Since this is a database problem, Go is not applicable in the traditional LeetCode sense. The correct submission language is SQL. However, conceptually, the same logic in Go would look like this:

package main

import (
	"sort"
)

func getNthHighestSalary(salaries []int, n int) *int {
	distinctMap := make(map[int]bool)

	for _, salary := range salaries {
		distinctMap[salary] = true
	}

	distinctSalaries := []int{}

	for salary := range distinctMap {
		distinctSalaries = append(distinctSalaries, salary)
	}

	sort.Sort(sort.Reverse(sort.IntSlice(distinctSalaries)))

	if n > len(distinctSalaries) {
		return nil
	}

	result := distinctSalaries[n-1]
	return &result
}

The Go implementation mirrors the SQL logic:

A map removes duplicate salaries
The distinct salaries are sorted descending
The n - 1 indexed value is returned
nil represents the absence of a valid answer

Unlike SQL, Go requires explicit handling for duplicate removal and nullability.

Worked Examples

Example 1

Input:

Employee:
1 -> 100
2 -> 200
3 -> 300

n = 2

Step 1: Extract distinct salaries

Salaries
100
200
300

No duplicates exist.

Step 2: Sort descending

Rank	Salary
1	300
2	200
3	100

Step 3: Apply OFFSET

Since n = 2:

OFFSET = n - 1 = 1

Skip the first row:

Remaining Salaries
200
100

Step 4: LIMIT 1

Return:

Final output:

getNthHighestSalary(2)
200

Example 2

Input:

Employee:
1 -> 100

n = 2

Step 1: Extract distinct salaries

Salaries
100

Step 2: Sort descending

Rank	Salary
1	100

Step 3: Apply OFFSET

OFFSET = 1

After skipping one row:

Remaining Salaries
empty

Step 4: LIMIT 1

No row exists.

SQL returns:

NULL

Final output:

getNthHighestSalary(2)
null

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting distinct salaries dominates the runtime
Space	O(n)	Distinct salary storage may require additional memory

The expensive operation is sorting the distinct salary values. If there are k distinct salaries, sorting requires O(k log k) time. In the worst case, all salaries are unique, so k = n.

Space complexity depends on the database engine implementation of DISTINCT and sorting. Some engines may use temporary structures to store intermediate results.

Test Cases

# Example 1
assert getNthHighestSalary([100, 200, 300], 2) == 200  # second highest distinct salary

# Example 2
assert getNthHighestSalary([100], 2) is None  # fewer than n distinct salaries

# Duplicate salaries
assert getNthHighestSalary([100, 200, 200, 300], 2) == 200  # duplicates ignored

# Highest salary
assert getNthHighestSalary([50, 60, 70], 1) == 70  # first highest salary

# Last distinct salary
assert getNthHighestSalary([10, 20, 30], 3) == 10  # lowest distinct salary

# n larger than distinct count
assert getNthHighestSalary([1, 2, 3], 5) is None  # invalid rank

# All salaries identical
assert getNthHighestSalary([100, 100, 100], 1) == 100  # only one distinct salary

# All salaries identical with larger n
assert getNthHighestSalary([100, 100, 100], 2) is None  # no second distinct salary

# Non-consecutive salaries
assert getNthHighestSalary([500, 1000, 750], 2) == 750  # ranking independent of gaps

Test Summary

Test	Why
`[100,200,300], n=2`	Validates standard ranking
`[100], n=2`	Validates null behavior
Duplicate salaries	Ensures distinct handling
`n=1`	Checks highest salary retrieval
Last rank	Verifies lower boundary
Large `n`	Ensures out-of-range handling
All identical salaries	Tests duplicate collapse
All identical with larger `n`	Ensures null after deduplication
Non-consecutive values	Confirms ordering logic

Edge Cases

Duplicate Salaries

A common mistake is treating duplicate salary rows as separate rankings. For example:

100, 200, 200, 300

The second highest distinct salary is still 200, not the second row after sorting.

The implementation avoids this bug by using DISTINCT, ensuring every salary value appears only once before ranking.

Fewer Than N Distinct Salaries

If the table contains fewer distinct salaries than requested, the answer must be NULL.

For example:

Salaries: 100
n = 2

After applying the offset, no row remains. SQL naturally returns NULL, so no additional logic is required.

All Salaries Identical

When every employee has the same salary:

100, 100, 100

There is only one distinct salary.

A naive implementation might incorrectly count duplicates and think a second highest salary exists. Using DISTINCT guarantees that only unique salary values participate in ranking.

Non-Consecutive Salary Values

Salary rankings depend on order, not arithmetic gaps.

For example:

1000, 750, 500

The second highest salary is 750, regardless of the numeric distance between values.

Sorting descending correctly handles this scenario without any special logic.