Domain 1EasyCORE

Second Highest Salary

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.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#**FAANG asked:** 1

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 Employee with at least one column Salary.

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:

  1. Duplicates: There might be duplicate salaries, but we need to consider only unique salaries.
  2. Single Salary: If there is only one unique salary, the second highest should be NULL.
  3. 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

  1. Initialize Variables:

    • first to store the highest salary (initialized to negative infinity).
    • second to store the second highest salary (initialized to negative infinity).
  2. Iterate Through Salaries:

    • For each salary in the table:
      • If the salary is greater than first, update second to be first and then update first to be this salary.
      • Else if the salary is greater than second and not equal to first, update second to be this salary.
  3. Return Result:

    • If second remains negative infinity, it means there was no second highest unique salary, so return NULL.
    • Otherwise, return second.

Complexity Analysis

  • Time Complexity: (O(n)), where (n) is the number of rows in the Employee table. 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 NULL because there are no salaries to compare.
  • Single Salary: If all salaries are the same, second will remain -2147483648, and the outer query will return NULL.
  • Duplicates: The use of DISTINCT ensures that only unique salaries are considered.