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 nth highest salary from the Employee table. If there is no nth highest salary, 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 | +------------------------+
The Nth Highest Salary problem focuses on retrieving the salary that ranks N when employee salaries are ordered from highest to lowest. A key detail is that duplicate salaries should be treated carefully, meaning the ranking is usually based on distinct salary values.
A common strategy is to first isolate unique salaries using DISTINCT, then sort them in descending order and locate the Nth value using pagination techniques like LIMIT with an offset. Another popular approach is to use SQL window functions such as DENSE_RANK() to assign ranks to salaries and then filter for the desired rank.
Both methods rely on sorting the salary column, which typically dominates the runtime. The window function method is often more expressive and easier to extend for similar ranking queries. Care should also be taken to handle cases where the requested rank does not exist, returning NULL instead of an empty result.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| DISTINCT + ORDER BY with LIMIT/OFFSET | O(n log n) | O(n) |
| Window Function (DENSE_RANK) | O(n log n) | O(n) |
| Subquery with COUNT of DISTINCT Salaries | O(n^2) worst case | O(1) |
Gate Smashers
This approach uses the SQL query constructs to fetch the nth highest salary directly from the database. We will utilize ORDER BY, DISTINCT, LIMIT, and OFFSET to achieve this.
Steps:
SELECT DISTINCT.ORDER BY salary DESC.LIMIT and OFFSET to skip the first n-1 results and take the nth result if it exists.1# Placeholder function for SQL query in Python
2def get_nth_highest_salary_sql(n):
3 return f"SELECT DISTINCT salary FROM Employee ORDER BY salary DESC LIMIT 1 OFFSET {n-1}"
4
5# Execute this query using a Python SQL library like sqlite3 or SQLAlchemy.This Python function generates a SQL query string. Execute this query using libraries like sqlite3 or SQLAlchemy in a database context.
In this approach, we will use the DENSE_RANK() window function available in SQL to assign ranks to salaries based on their value.
Steps:
DENSE_RANK by partitioning properly.n.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of this SQL problem are common in technical interviews at large tech companies. It tests understanding of ranking, aggregation, and SQL query design.
A common optimal approach is to select distinct salaries, sort them in descending order, and retrieve the Nth entry using LIMIT with an offset. Another clean method uses the DENSE_RANK() window function to rank salaries and filter for the desired rank.
DISTINCT ensures that duplicate salary values do not affect ranking. Without it, multiple employees with the same salary could incorrectly shift the position of the Nth highest value.
Yes, window functions like DENSE_RANK() are often used for this problem. They assign ranks to salary values based on ordering, allowing you to easily filter rows where the rank equals N.
This Java method constructs an advanced SQL query using the DENSE_RANK function, which ranks salaries and retrieves the nth highest ranked salary. Execution requires a database backend with SQL window function support.