Write a query to find the second highest salary.

A simple way to retrieve the second highest salary is to order the salaries in descending order and skip the first row. In SQL you can use LIMIT/OFFSET (MySQL, PostgreSQL) or ROW_NUMBER() (SQL Server, Oracle). Example for MySQL/PostgreSQL:

SELECT DISTINCT salary

FROM employee

ORDER BY salary DESC

LIMIT 1 OFFSET 1;

This returns the second distinct salary value. If you need the employee(s) who earn that salary, you can wrap the above in a subquery:

SELECT e.*

FROM employee e

WHERE e.salary = (

SELECT DISTINCT salary

FROM employee

ORDER BY salary DESC

LIMIT 1 OFFSET 1

);

Complexity: The query scans the salary column once, so it is O(n) time with a single pass and O(1) additional space if the database can use an index on salary. If the table is large, ensure an index on salary to keep the operation efficient.