Fast and easy PostgreSQL solution using window function 🐘
Intuition\nTo solve the problem of finding the nth highest salary, my initial thought is to use ranking. Using the window function DENSE_RANK() makes sense beca
# Intuition\nTo solve the problem of finding the nth highest salary, my initial thought is to use ranking. Using the window function `DENSE_RANK()` makes sense because it assigns ranks to rows without gaps. This way, even if multiple employees have the same salary, they\'ll be assigned the same rank, allowing to identify the nth highest salary.\n\n\n# Approach\nI use a subquery to select salaries from the `Employee` table and apply the `DENSE_RANK()` function to assign a rank to each salary, ordered in descending order. This ranking is done in a way that salaries are considered from highest to lowest, with duplicates being ranked the same. By filtering the ranked salaries where the rank equals the input parameter `N`, we can pinpoint the nth highest salary. Limiting the results to 1 ensures that even if multiple salaries share the nth rank, only one is returned.\n\n# Complexity\n- **Time complexity:** $$O(n\\ log(n))$$ due to the sorting operation in the `DENSE_RANK()` window function. \n\n- **Space complexity:** $$O(n)$$ because window function needs to compute a rank for each of the $$n$$ rows in `Employee` table. \n\n# Code\n```PostgreSQL []\nCREATE OR REPLACE FUNCTION NthHighestSalary(N INT) RETURNS TABLE (Salary INT) AS $\nBEGIN\n  RETURN QUERY (\n    select a.salary\n    from (select e.salary, dense_rank() over (order by e.salary desc) r from Employee e) a\n    where a.r = n\n    limit 1\n  );\nEND;\n$ LANGUAGE plpgsql;\n```\n\n\uD83C\uDF40 Good luck everyone \uD83C\uDF40\n
['PostgreSQL']