176. Second Highest Salary
Model: qwen2.5-coder:14b
Topics:
FAANG asked: 1
Acceptance rate: 33.5%
Problem Breakdown
The problem asks us to find the second highest salary from a table named Employee. The table has at least one column named Salary, which contains the salaries of employees.
Inputs:
- A table
Employeewith at least one columnSalary.
Outputs:
- The second highest unique salary. If there is no such salary (e.g., all salaries are the same or only one salary exists), return
NULL.
Implicit Constraints and Edge Cases:
- Duplicates: There might be duplicate salaries, but we need to consider only unique salaries.
- Single Salary: If there is only one unique salary, the second highest should be
NULL. - Empty Table: If the table is empty, return
NULL.
Intuition
A brute-force approach would involve sorting all the salaries in descending order and then selecting the second element. However, this approach has a time complexity of (O(n \log n)) due to sorting.
The key insight is that we don’t need to sort all the salaries. Instead, we can keep track of the highest and second highest unique salaries as we iterate through the list once. This reduces the time complexity to (O(n)).
Approach
-
Initialize Variables:
firstto store the highest salary (initialized to negative infinity).secondto store the second highest salary (initialized to negative infinity).
-
Iterate Through Salaries:
- For each salary in the table:
- If the salary is greater than
first, updatesecondto befirstand then updatefirstto be this salary. - Else if the salary is greater than
secondand not equal tofirst, updatesecondto be this salary.
- If the salary is greater than
- For each salary in the table:
-
Return Result:
- If
secondremains negative infinity, it means there was no second highest unique salary, so returnNULL. - Otherwise, return
second.
- If
Complexity Analysis
- Time Complexity: (O(n)), where (n) is the number of rows in the
Employeetable. We only need to iterate through the list once. - Space Complexity: (O(1)), as we are using a constant amount of extra space.
Solution
SELECT
CASE
WHEN second = -2147483648 THEN NULL
ELSE second
END AS SecondHighestSalary
FROM (
SELECT DISTINCT Salary,
MAX(Salary) OVER () AS first,
MAX(CASE WHEN Salary < MAX(Salary) OVER () THEN Salary END) OVER () AS second
FROM Employee
) subquery;
Edge Cases Handled
- Empty Table: The query will return
NULLbecause there are no salaries to compare. - Single Salary: If all salaries are the same,
secondwill remain-2147483648, and the outer query will returnNULL. - Duplicates: The use of
DISTINCTensures that only unique salaries are considered.