Find second smallest and second largest element in array

medium

By - Aman Pareek

Last Updated - 27/08/2024

Problem Statement

Given an array of integers, return a new array where:

The 0th position contains the second smallest element in the original array.
The 1st position contains the second largest element in the original array.

If there are fewer than two unique elements in the array, return null for the respective missing element.

Example 1

Input: array = [1, 2, 3, 4, 5]

Output: [2, 4]

Example 2

Input: array = [5, 5, 5, 5]

Output: [null, null]

Example 3

Input: array = [1, 1, 2, 2, 3]

Output: [2, 2]

Example 4

Input: number = 4

Output: Throw error => Input must be an array

Solution 1: Using Sorting

function findSecondSmallestAndLargest(arr) {
    if (!Array.isArray(arr)) {
        throw new Error('Input must be an array');
    }

    const uniqueSorted = Array.from(new Set(arr)).sort((a, b) => a - b);

    const secondSmallest = uniqueSorted.length > 1 ? uniqueSorted[1] : null;
    const secondLargest = uniqueSorted.length > 1 ? uniqueSorted[uniqueSorted.length - 2] : null;

    return [secondSmallest, secondLargest];
} 

const array1 = [1, 2, 3, 4, 5];
findSecondSmallestAndLargest(array1);  //output: [2, 4] 

const array2 = [5, 5, 5, 5];
findSecondSmallestAndLargest(array2);  //output: [null, null] 

const array3 = [1, 1, 2, 2, 3];
findSecondSmallestAndLargest(array3);  //output: [2, 2] 

const number4 = 4;
findSecondSmallestAndLargest(number4);  //Throw error => Input must be an array

A hash map (or dictionary) is a great way to solve this problem eff…

Solution 2: Using Two Passes

function findSecondSmallestAndLargestTwoPass(arr) {
    if (!Array.isArray(arr)) {
        throw new Error('Input must be an array');
    }

    const uniqueSet = new Set(arr);
    if (uniqueSet.size < 2) {
        return [null, null];
    }

    let min = Infinity;
    let secondMin = Infinity;
    let max = -Infinity;
    let secondMax = -Infinity;

    for (const num of uniqueSet) {
        if (num < min) {
            secondMin = min;
            min = num;
        } else if (num < secondMin && num !== min) {
            secondMin = num;
        }

        if (num > max) {
            secondMax = max;
            max = num;
        } else if (num > secondMax && num !== max) {
            secondMax = num;
        }
    }

    return [secondMin === Infinity ? null : secondMin, secondMax === -Infinity ? null : secondMax];
} 

const array1 = [1, 2, 3, 4, 5];
findSecondSmallestAndLargestTwoPass(array1);  //output: [2, 4] 

const array2 = [5, 5, 5, 5];
findSecondSmallestAndLargestTwoPass(array2);  //output: [null, null] 

const array3 = [1, 1, 2, 2, 3];
findSecondSmallestAndLargestTwoPass(array3);  //output: [2, 2] 

const number4 = 4;
findSecondSmallestAndLargestTwoPass(number4);  //Throw error => Input must be an array

Solution 3: Using Single Pass

function findSecondSmallestAndLargestSinglePass(arr) {
    if (!Array.isArray(arr)) {
        throw new Error('Input must be an array');
    }

    let min = Infinity;
    let secondMin = Infinity;
    let max = -Infinity;
    let secondMax = -Infinity;

    for (const num of arr) {
        if (num < min) {
            secondMin = min;
            min = num;
        } else if (num < secondMin && num !== min) {
            secondMin = num;
        }

        if (num > max) {
            secondMax = max;
            max = num;
        } else if (num > secondMax && num !== max) {
            secondMax = num;
        }
    }

    return [secondMin === Infinity ? null : secondMin, secondMax === -Infinity ? null : secondMax];
} 

const array1 = [1, 2, 3, 4, 5];
findSecondSmallestAndLargestSinglePass(array1);  //output: [2, 4] 

const array2 = [5, 5, 5, 5];
findSecondSmallestAndLargestSinglePass(array2);  //output: [null, null] 

const array3 = [1, 1, 2, 2, 3];
findSecondSmallestAndLargestSinglePass(array3);  //output: [2, 2] 

const number4 = 4;
findSecondSmallestAndLargestSinglePass(number4);  //Throw error => Input must be an array