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
2#include <stdio.h>
3#include <sqlite3.h>
4
5int main() {
6 sqlite3 *db;
7 sqlite3_open("company.db", &db);
8 const char *sql = "SELECT MAX(salary) AS SecondHighestSalary FROM Employee WHERE salary < (SELECT MAX(salary) FROM Employee);";
9 // Execute SQL and handle results
10 sqlite3_close(db);
11 return 0;
12}
13This C solution uses sqlite3 to connect to a database and execute a SQL query that selects the second highest salary from the Employee table. The MAX function is used within a sub-query to find and exclude the highest salary, thereby obtaining the second highest.
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
2const sqlite3 = require('sqlite3').verbose
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 JavaScript solution uses the sqlite3 library to retrieve salaries from the Employee table. It then utilizes ES6 Set to filter unique salaries and sorts them in descending order. The second element in the array gives us the second highest salary or 'None' if absent.