Second Highest Salary

Naive Solution

The most straightforward way to find the second highest salary is to first find all distinct salaries, sort them in descending order, and then select the second element. If there are fewer than two distinct salaries, return null.

SQL Code

SELECT MAX(salary) AS SecondHighestSalary
FROM Employee
WHERE salary < (SELECT MAX(salary) FROM Employee);

Explanation

This SQL query first finds the maximum salary. Then, it selects the maximum salary from the remaining salaries that are less than the maximum salary found in the first step.

Big O Analysis

• Time Complexity: O(n), where n is the number of rows in the Employee table. The subquery SELECT MAX(salary) FROM Employee takes O(n) time. The outer query SELECT MAX(salary) FROM Employee WHERE salary < ... also takes O(n) in the worst-case scenario.
• Space Complexity: O(1). The space complexity is constant because we are only storing a few scalar values.

Edge Cases

• If the table is empty, both queries will return NULL, and the final result will be NULL.
• If there is only one distinct salary, the inner query will return the maximum salary, and the outer query will search for salaries less than that, resulting in an empty set and a final result of NULL.
• If all salaries are the same, the query will also return NULL.

Optimal Solution

An improved solution uses LIMIT and OFFSET to directly retrieve the second highest distinct salary. This approach is often more efficient, especially for large tables.

SQL Code

SELECT DISTINCT salary AS SecondHighestSalary
FROM Employee
ORDER BY salary DESC
LIMIT 1 OFFSET 1;

To handle the case where there is no second highest salary, we can wrap the above query in another SELECT statement that returns NULL if the inner query returns an empty set. Using IFNULL

SELECT
    IFNULL(
      (SELECT DISTINCT salary
       FROM Employee
       ORDER BY salary DESC
       LIMIT 1 OFFSET 1), NULL) AS SecondHighestSalary;

Explanation

1. SELECT DISTINCT salary FROM Employee: This selects all distinct salaries from the Employee table.
2. ORDER BY salary DESC: This sorts the distinct salaries in descending order.
3. LIMIT 1 OFFSET 1: This selects the first row (LIMIT 1) after skipping the first row (OFFSET 1), effectively selecting the second highest salary.
4. IFNULL(..., NULL): This handles the case where the subquery returns an empty set (i.e., there is no second highest salary). If the subquery returns NULL, the outer query returns NULL. Using IFNULL ensures the correct output according to the problem description when there is no second highest salary.

Big O Analysis

• Time Complexity: O(n log n) in the worst case for sorting. However, many databases are optimized for LIMIT queries, potentially making it more efficient than the naive solution, especially for larger datasets. Often this can be closer to O(n).
• Space Complexity: O(n) in the worst case, due to sorting. However, the distinct operation could reduce the data significantly.

Edge Cases

• If the table is empty, the query will return NULL.
• If there is only one distinct salary, the OFFSET will cause the query to return an empty set, and the IFNULL function will return NULL.
• If all salaries are identical, the query will return NULL because the OFFSET will skip the only distinct value.