thesarfo

Reference

Second Largest Element

Finding the second largest element in an array in a single pass, without sorting, handling duplicates correctly.

views 0

Find the second largest element in an array, without sorting (and handling duplicates correctly).

Brute force: find the largest first, then loop again for the largest value that isn’t equal to it.

int getSecondLargest(int[] arr, int n){
    int largest = arr[0];
    for(int i = 0; i < n; i++){
        if(arr[i] > largest){
            largest = arr[i];
        }
    }


    int slargest = -1;
    for(int i = 0; i < n; i++){
        if(arr[i] > slargest && arr[i] != largest){
            slargest = arr[i];
        }
    }
    return slargest;
}

Optimal (single pass): track both largest and second-largest as you go. Whenever a new largest is found, the old largest becomes the new second-largest.

int secondLargest(vector<int> &a, int n){
    int largest = a[0];
    int slargest = -1;


    for (int i = 1; i < n; i++){
        if(a[i] > largest){
            slargest = largest;
            largest = a[i];
        }
        else if(a[i] < largest && a[i] > slargest){
            slargest = a[i];
        }
    }
    return slargest;
}