C++ Program to Find Second Largest in Array

To find the second largest element in an array in C++, iterate through the array keeping track of the largest and second largest values using if conditions, for example: if(arr[i] > largest) { secondLargest = largest; largest = arr[i]; } else if(arr[i] > secondLargest && arr[i] != largest) { secondLargest = arr[i]; }.

Examples

Inputarr = {5, 3, 9, 1, 6}

Output6

Inputarr = {10, 10, 9, 8}

Output9

Inputarr = {1, 1, 1, 1}

OutputNo second largest element

How to Think About It

To find the second largest number, first find the largest number by comparing each element. Then keep track of the next biggest number that is less than the largest. This way, you only need one pass through the array, updating two variables as you go.

Algorithm

1

Initialize two variables: largest and secondLargest with minimum possible values.

2

Loop through each element in the array.

3

If the current element is greater than largest, update secondLargest to largest and largest to current element.

4

Else if the current element is greater than secondLargest and not equal to largest, update secondLargest to current element.

5

After the loop, check if secondLargest was updated; if not, report no second largest element.

6

Return or print the secondLargest value.

Code

cpp

#include <iostream>
#include <climits>
using namespace std;

int main() {
    int arr[] = {5, 3, 9, 1, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int largest = INT_MIN, secondLargest = INT_MIN;

    for(int i = 0; i < n; i++) {
        if(arr[i] > largest) {
            secondLargest = largest;
            largest = arr[i];
        } else if(arr[i] > secondLargest && arr[i] != largest) {
            secondLargest = arr[i];
        }
    }

    if(secondLargest == INT_MIN) {
        cout << "No second largest element" << endl;
    } else {
        cout << secondLargest << endl;
    }
    return 0;
}

Output

6

Dry Run

Let's trace the array {5, 3, 9, 1, 6} through the code

1

Initialize

largest = INT_MIN, secondLargest = INT_MIN

2

Check 5

5 > largest(INT_MIN), so largest=5, secondLargest=INT_MIN

3

Check 3

3 > secondLargest(INT_MIN) and 3 != largest(5), so secondLargest=3

4

Check 9

9 > largest(5), so secondLargest=largest(5), largest=9

5

Check 1

1 > secondLargest(5)? No, no change

6

Check 6

6 > secondLargest(5) and 6 != largest(9), so secondLargest=6

Iteration	Element	largest	secondLargest
1	5	5	INT_MIN
2	3	5	3
3	9	9	5
4	1	9	5
5	6	9	6

Why This Works

Step 1: Track largest and second largest

We keep two variables to remember the biggest and second biggest numbers found so far using largest and secondLargest.

Step 2: Update when bigger found

If a number is bigger than largest, it becomes the new largest and the old largest becomes second largest.

Step 3: Update second largest carefully

If a number is not bigger than largest but bigger than second largest and not equal to largest, update second largest.

Alternative Approaches

Sort the array and pick second last element

cpp

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int arr[] = {5, 3, 9, 1, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    sort(arr, arr + n);
    int largest = arr[n-1];
    int secondLargest = INT_MIN;
    for(int i = n-2; i >= 0; i--) {
        if(arr[i] != largest) {
            secondLargest = arr[i];
            break;
        }
    }
    if(secondLargest == INT_MIN) cout << "No second largest element" << endl;
    else cout << secondLargest << endl;
    return 0;
}

This method is simpler but slower because sorting takes O(n log n) time.

Use set to store unique elements and pick second largest

cpp

#include <iostream>
#include <set>
using namespace std;

int main() {
    int arr[] = {5, 3, 9, 1, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    set<int> s(arr, arr + n);
    if(s.size() < 2) {
        cout << "No second largest element" << endl;
    } else {
        auto it = s.rbegin();
        ++it;
        cout << *it << endl;
    }
    return 0;
}

This approach uses extra memory but handles duplicates easily and is clean.

Complexity: O(n) time, O(1) space

Time Complexity

The program loops through the array once, so time complexity is O(n), where n is the number of elements.

Space Complexity

Only two extra variables are used regardless of input size, so space complexity is O(1).

Which Approach is Fastest?

The single pass method is fastest with O(n) time, while sorting takes O(n log n) and using a set adds extra memory overhead.

Approach	Time	Space	Best For
Single pass tracking	O(n)	O(1)	Fastest and memory efficient
Sorting array	O(n log n)	O(1)	Simple but slower for large arrays
Using set	O(n log n)	O(n)	Handles duplicates easily, uses extra memory