Second Highest Salary - Solution & Explanation

Problem Overview: The Employee table contains salaries for multiple employees. Your task is to return the second highest salary. If a second distinct salary does not exist, the query should return NULL. The challenge is handling duplicates and ensuring the result reflects the second distinct value.

Approach 1: MAX with Subquery (O(n) time, O(1) space)

This approach scans the table twice using SQL aggregation. First, compute the maximum salary using MAX(Salary). Then run a second query that finds the maximum salary strictly less than that value. The key insight is that the second highest salary must be the largest value smaller than the overall maximum. SQL handles the comparison efficiently using a subquery: SELECT MAX(Salary) FROM Employee WHERE Salary < (SELECT MAX(Salary) FROM Employee). Database engines typically perform table scans for these aggregations, resulting in O(n) time complexity with constant extra space. This method is widely used in interviews because it clearly expresses the logical definition of "second highest." It relies entirely on SQL aggregation and comparison operations from database fundamentals.

Approach 2: ORDER BY with LIMIT/OFFSET (O(n log n) time, O(1) space)

This strategy sorts salaries in descending order and selects the second distinct value. The query uses SELECT DISTINCT Salary FROM Employee ORDER BY Salary DESC LIMIT 1 OFFSET 1. Sorting ensures the highest salary appears first and the second highest appears next. The DISTINCT keyword removes duplicates so repeated salaries do not interfere with the ranking. Sorting typically costs O(n log n) time in the database engine. The advantage is simplicity—this pattern reads like a ranking query and is easy to modify for the third or fourth highest salary. This approach demonstrates practical use of SQL ordering and pagination features.

Approach 3: Language-Specific Processing After Fetch (O(n) time, O(1) space)

In application code (Java, JavaScript, Python, or C), you can fetch salaries and compute the result manually. Iterate through all values while tracking the highest and second highest distinct numbers. Each iteration compares the current salary with the tracked values and updates them accordingly. This requires only a single pass through the data, giving O(n) time complexity and constant memory. The approach highlights basic algorithm reasoning and works well when salary data is already loaded in memory.

Recommended for interviews: The MAX with subquery approach is the most common expectation for SQL interviews. It shows you understand aggregation, filtering, and query composition. Sorting with ORDER BY is also valid but less optimal because of the sorting cost. Implementing the logic in application code demonstrates algorithmic thinking, but interviewers typically prefer a pure SQL solution when the problem is labeled as a database question.