Find Second Highest Salary

TCS NQT Coding Easy Go Ad-Free - ₹20/mo

Write a SQL query to find the second-highest salary from an employee table. The table has a column named 'salary' containing integer values. Assume there are at least two distinct salary values in the table.

Examples:

Input: Employee table with salaries: [100, 200, 300]

Output: 200

Explanation: The distinct salaries are 100, 200, and 300. The second-highest salary is 200.

Input: Employee table with salaries: [500, 500, 400]

Output: 400

Input: Employee table with salaries: [1000, 800, 800, 600]

Output: 800

Constraints

Salaries are positive integers.
The table contains at least two distinct salary values.
The number of rows can be large, so the query should be optimized for efficiency.

Editorial

Intuition:

The goal is to find the second highest distinct salary. Instead of sorting, we can track the highest and second highest distinct values in a single pass, ensuring optimal performance for large datasets.

Approach:

Initialize two variables, first and second, to -1 (since salaries are positive integers).
Iterate through each salary in the input list.
For each salary:
- If the salary is greater than first, update second to the old first and first to the current salary.
- Else if the salary is greater than second and not equal to first, update second to the current salary.
After processing all salaries, second contains the second highest distinct salary.

#include <vector>
using namespace std;
int secondHighest(vector& salaries) {
    int first = -1, second = -1;
    for (int salary : salaries) {
        if (salary > first) {
            second = first;
            first = salary;
        } else if (salary > second && salary != first) {
            second = salary;
        }
    }
    return second;
}
public int secondHighest(int[] salaries) {
    int first = -1, second = -1;
    for (int salary : salaries) {
        if (salary > first) {
            second = first;
            first = salary;
        } else if (salary > second && salary != first) {
            second = salary;
        }
    }
    return second;
}
def second_highest(salaries):
    first = -1
    second = -1
    for salary in salaries:
        if salary > first:
            second = first
            first = salary
        elif salary > second and salary != first:
            second = salary
    return second
function secondHighest(salaries) {
    let first = -1, second = -1;
    for (let salary of salaries) {
        if (salary > first) {
            second = first;
            first = salary;
        } else if (salary > second && salary != first) {
            second = salary;
        }
    }
    return second;
}

Complexity Analysis:

Time Complexity: O(n), where n is the number of salaries. We traverse the list exactly once.

Space Complexity: O(1), as we only use two additional integer variables regardless of input size.

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories