Practice/Amazon/Leetcode 177. Nth Highest Salary

Leetcode 177. Nth Highest Salary

CodingOptional

Problem

You are given a list of employee salaries and an integer k. Your task is to find the kth largest unique salary from the list. If there are fewer than k unique salaries, return null.

Note that salaries may contain duplicates, but you should only consider each unique salary value once when determining the ranking.

Requirements

1. Identify all unique salary values from the input list
2. Rank these unique salaries in descending order
3. Return the kth largest unique salary (1-indexed)
4. Return null if k is greater than the number of unique salaries
5. Return null if the input list is empty

Constraints

• 0 ≤ salaries.length ≤ 104
• 1 ≤ k ≤ 104
• 0 ≤ salaries[i] ≤ 106
• Expected time complexity: O(n log n) or better
• Expected space complexity: O(n)

Examples

Example 1:

Input: salaries = [50000, 80000, 60000, 80000, 70000], k = 2 Output: 70000 Explanation: The unique salaries are \{50000, 60000, 70000, 80000\}. Sorted in descending order: [80000, 70000, 60000, 50000]. The 2nd largest is 70000.

Example 2:

Input: salaries = [100000, 100000, 100000], k = 2 Output: null Explanation: There is only one unique salary (100000), so there is no 2nd largest salary.

Example 3:

Input: salaries = [45000, 55000, 65000, 75000], k = 1 Output: 75000 Explanation: The highest unique salary is 75000.