Nth Highest Salary

This challenge involves retrieving the Nth highest salary from a given list of employee salaries. This is a common problem in data analysis and database management, often used to identify top performers or understand salary distributions.

Problem Description

Given a list of employee salaries, your task is to find the Nth highest unique salary. This means if there are duplicate salaries, they should be treated as a single distinct salary when determining the Nth highest. For example, if the salaries are [100, 200, 200, 300], the 1st highest salary is 300, the 2nd highest is 200, and the 3rd highest is 100.

Key Requirements:

• You will be provided with a list of numerical values representing salaries and an integer N.
• You need to return the Nth highest distinct salary.
• If there are fewer than N distinct salaries, you should indicate this (e.g., return a specific value like null, -1, or raise an error, depending on language conventions).

Expected Behavior:

• The function should handle cases where N is 1 (highest salary).
• The function should handle cases where N is greater than the number of distinct salaries.
• The function should correctly identify the Nth highest salary even with duplicate salary values.

Edge Cases:

• An empty list of salaries.
• N being zero or negative (though typically N will be a positive integer).
• A list with only one unique salary.

Examples

Example 1:

Input: salaries = [100, 50, 200, 150, 200], N = 2
Output: 150
Explanation: The distinct salaries are [50, 100, 150, 200]. The 1st highest is 200, and the 2nd highest is 150.

Example 2:

Input: salaries = [1000, 1000, 1000], N = 1
Output: 1000
Explanation: The only distinct salary is 1000. The 1st highest is 1000.

Example 3:

Input: salaries = [500, 600], N = 3
Output: null (or -1, or equivalent for "not found")
Explanation: There are only two distinct salaries (500, 600). Since N=3 is greater than the number of distinct salaries, the 3rd highest does not exist.

Example 4:

Input: salaries = [], N = 1
Output: null (or -1, or equivalent for "not found")
Explanation: The list of salaries is empty, so no highest salary can be found.

Constraints

• The number of salaries in the input list will be between 0 and 1,000,000.
• Each salary will be a non-negative integer between 0 and 1,000,000,000.
• N will be a positive integer between 1 and 1,000,000.
• The solution should aim for an efficient time complexity, ideally better than O(n log n) if possible, but O(n log n) is acceptable.

Notes

• Consider how you will handle duplicate salaries to ensure you are finding the Nth distinct highest salary.
• Think about different data structures that might be useful for this problem (e.g., sets, sorted lists, heaps).
• The exact return value for "not found" will depend on the conventions of the language you are using, but it should be clearly documented or agreed upon beforehand. For this challenge, null or -1 are common indicators.