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 second highest distinct salary from the Employee table. If there is no second highest salary, return null (return None in Pandas).
The result format is in the following example.
Example 1:
Input: Employee table: +----+--------+ | id | salary | +----+--------+ | 1 | 100 | | 2 | 200 | | 3 | 300 | +----+--------+ Output: +---------------------+ | SecondHighestSalary | +---------------------+ | 200 | +---------------------+
Example 2:
Input: Employee table: +----+--------+ | id | salary | +----+--------+ | 1 | 100 | +----+--------+ Output: +---------------------+ | SecondHighestSalary | +---------------------+ | null | +---------------------+
The Second Highest Salary problem tests your ability to query ranked values from a database table. The key idea is to retrieve the salary that is just below the maximum without returning duplicates. A common approach is to first identify the highest salary and then query for the MAX(salary) that is strictly less than that value. This technique uses a subquery and works well when dealing with distinct salary values.
Another popular strategy uses sorting with pagination. By selecting DISTINCT salary, ordering them in descending order, and using LIMIT with an offset, you can directly access the second entry in the ordered list. This approach is concise and frequently used in interview settings when SQL dialects support LIMIT/OFFSET.
Be mindful of edge cases where a second highest value does not exist. Many solutions wrap the query using functions such as IFNULL or equivalent constructs to return NULL when no valid result is found. Both strategies are efficient for typical database sizes and demonstrate strong SQL query composition skills.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Subquery with MAX and comparison | O(n) | O(1) |
| DISTINCT + ORDER BY with LIMIT/OFFSET | O(n log n) | O(1) |
Frederik Müller
This approach involves directly querying the database to retrieve the second highest distinct salary. The SQL query utilizes the MAX function in a subquery to exclude the highest salary from consideration, thus efficiently targeting the second highest.
Time Complexity: O(n) - Iterating through database rows
Space Complexity: O(1) - Constant additional space
1
2import sqlite3
3
4conn = sqlite3.connect('company.db')
5cursor = conn.cursor()
6
7query = """
8SELECT MAX(salary) AS SecondHighestSalary FROM Employee
9WHERE salary < (SELECT MAX(salary) FROM Employee);
10"""
11cursor.execute(query)
12result = cursor.fetchone()[0]
13
14conn.close()
15
16print(result if result is not None else 'None')
17This Python solution uses sqlite3 to execute a SQL query that selects the second highest salary from the Employee table. It uses a sub-query to fetch the maximum salary and exclude it to find the second maximum.
This approach does not rely on SQL but instead employs language-specific paradigms, such as sorting or managing unique salary values in a list or array, to identify the second highest distinct salary.
Time Complexity: O(n log n) - Due to TreeSet insertion
Space Complexity: O(n) - Storage for unique salaries
1
2import java.sql.Connection;
3
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 problem frequently appear in technical interviews at large tech companies. Interviewers use it to test SQL fundamentals, understanding of subqueries, and the ability to handle edge cases like duplicate or missing values.
A common optimal approach uses a subquery to first find the maximum salary and then selects the maximum salary that is smaller than it. This avoids sorting the entire dataset and directly identifies the second highest value using SQL aggregation.
Key SQL concepts include subqueries, aggregation functions like MAX, and filtering with comparison operators. Some solutions also rely on DISTINCT with ORDER BY and LIMIT/OFFSET to rank salary values.
Since this is a database query problem, the primary structure is a relational table. The logic relies on SQL query operations such as sorting, filtering, and aggregation rather than traditional in-memory data structures.
This Java solution uses JDBC to connect to the SQLite database, retrieves all salaries, and uses a TreeSet to store unique salaries in descending order. The second highest salary, if available, is then retrieved by skipping the first element (highest).