C++ Program to Find the Second Largest Number in an Array

Finding the second largest number in an array is a common problem that can be approached in various ways. This article will guide you through the implementation of a C++ program to find the second largest number in an array, providing multiple examples to demonstrate various solutions and their outputs.

Table of Contents

Prerequisites

Before diving into the implementation, you should have:

Basic understanding of C++ programming.
Familiarity with arrays and basic algorithms.

With these prerequisites, you will be able to grasp the concepts and code implementations discussed here.

1. Finding the Second Largest Number

1.1 Simple Approach

Let’s start with a simple approach to find the second largest number in an array by first sorting the array.

C++

#include <iostream>
#include <algorithm>

int findSecondLargest(int arr[], int n) {
    if (n < 2) {
        std::cout << "Array should have at least two elements" << std::endl;
        return -1; // Indicates error
    }

    std::sort(arr, arr + n); // Sort the array in ascending order

    // Traverse the sorted array from the end to find the first element which is not equal to the largest element
    for (int i = n - 2; i >= 0; i--) {
        if (arr[i] != arr[n - 1]) {
            return arr[i];
        }
    }

    return -1; // Indicates all elements are the same
}

int main() {
    int arr[] = {1, 2, 2, 3, 4, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    int secondLargest = findSecondLargest(arr, n);
    if (secondLargest != -1) {
        std::cout << "Second largest element: " << secondLargest << std::endl;
    }

    return 0;
}

1.2 Output Explanation

In this example, the input array is {1, 2, 2, 3, 4, 4, 5}. The program sorts the array and finds the second largest number.

C++

Second largest element: 4

1.3 Time Complexity

The time complexity of this approach is O(nlog⁡n)O(n \log n)O(nlogn) due to the sorting step.

2. Efficient Approach

2.1 Single Scan Approach

A more efficient way to find the second largest number is by scanning the array only once.

C++

#include <iostream>
#include <climits>

int findSecondLargest(int arr[], int n) {
    if (n < 2) {
        std::cout << "Array should have at least two elements" << std::endl;
        return -1; // Indicates error
    }

    int first = INT_MIN, second = INT_MIN;

    // Traverse the array
    for (int i = 0; i < n; i++) {
        if (arr[i] > first) {
            second = first;
            first = arr[i];
        } else if (arr[i] > second && arr[i] != first) {
            second = arr[i];
        }
    }

    if (second == INT_MIN) {
        std::cout << "No second largest element found" << std::endl;
        return -1;
    }

    return second;
}

int main() {
    int arr[] = {1, 2, 2, 3, 4, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    int secondLargest = findSecondLargest(arr, n);
    if (secondLargest != -1) {
        std::cout << "Second largest element: " << secondLargest << std::endl;
    }

    return 0;
}

2.2 Output Explanation

In this example, the input array is {1, 2, 2, 3, 4, 4, 5}. The program scans the array once to find the second largest number.

C++

Second largest element: 4

2.3 Time Complexity

The time complexity of this approach is O(n)O(n)O(n) as it only involves a single scan of the array.

3. Handling Edge Cases

3.1 Array with All Elements the Same

Let’s handle the edge case where all elements in the array are the same.

C++

int main() {
    int arr[] = {5, 5, 5, 5, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    int secondLargest = findSecondLargest(arr, n);
    if (secondLargest != -1) {
        std::cout << "Second largest element: " << secondLargest << std::endl;
    }

    return 0;
}

3.2 Output Explanation

In this example, the input array is {5, 5, 5, 5, 5}. The program scans the array but finds no second largest number since all elements are the same.

C++

No second largest element found

This ensures that the program handles edge cases gracefully without crashing.

Conclusion

A C++ program to find the second largest number in an array can be implemented using different approaches. The simple approach involves sorting the array, while the efficient approach uses a single scan of the array to find the second largest number. Handling edge cases where the array has fewer than two elements or all elements are the same ensures robustness.