Find second largest number in array

Find second maximum value in an array Problem

Input: arr = {25, 22, 25, 22, 9, 25, 9, 13, 7, 16, 3, 8, 8, 16, 11, 10, 10, 10, 13 }; 

Output: 22

Explanation: The problem statement is quite simple to understand. The input contains an unsorted array with multiple elements both unique and duplicate. The output is the second maximum value that is present in the array.

There are two approaches to solve it:

Case 1: Sort the array and find the second maximum value
Case 2: Using a single loop to iterate through elements to find the maximum and second maximum elements of the array.

# Brute Force

Algorithm

1. Pass the given array to the function to find the second maximum element.
2. The function sorts the array and returns the second maximum element from the position length-2.
3. Print the result on the screen.

Code:

#include <iostream>
using namespace std;
void getnum(int arr[], int l,int m,int r)
    {  
    int i, j, k; 
    int n1 = m - l + 1; 
    int n2 =  r - m; 
    int LA[n1], RA[n2];
    for (i = 0; i < n1; i++) 
        LA[i] = arr[l + i]; 
    for (j = 0; j < n2; j++) 
        RA[j] = arr[m + 1+ j];
    i = 0;
    j = 0; 
    k = l; 
    while (i < n1 && j < n2) 
    { 
        if (LA[i] <= RA[j]) 
        { 
            arr[k] = LA[i]; 
            i++; 
        } 
        else
        { 
            arr[k] = RA[j]; 
            j++; 
        } 
        k++; 
    } 
    while (i < n1) 
    { 
        arr[k] = LA[i]; 
        i++; 
        k++; 
    } 
    while (j < n2) 
    { 
        arr[k] = RA[j]; 
        j++; 
        k++; 
    } 
     
}  
void ms(int arr[],int l,int r)
{
    if (l < r) 
    { 
        int m = l+(r-l)/2;
        ms(arr, l, m); 
        ms(arr, m+1, r); 
        getnum(arr, l, m, r); 
    } 
}
int main()
{
    int arr[]={1,5,2,3,5,6,4,8};  
    int len=8;
    ms(arr,0,len-1);
    cout<<arr[len-2]<<endl;
    return 0;
}

Time Complexity : O(NlogN)

# Optimized Approach

1. Initialize the max and second max elements to min value.
2. Iterate through the array elements.
3. If the array element is greater than the max value update the max value with the array element and the second max value with the max element.
4. If the array element is greater than second max element but is not equal to the max element update the second max element with the array element.
5. Finally, print the second max value which is the second maximum value of the array.

Code:

#include <iostream>
#include<limits.h>
using namespace std;
    void getnum(int arr[], int len)
    {  
        int i, max, secondmax;
        if (len < 2) 
        { 
            cout<<" Invalid input size"; 
            return; 
        } 
        max = secondmax = INT_MIN; 
        for (i = 0; i < len ; i++) 
        {
            if (arr[i] > max) 
            { 
                secondmax = max; 
                max = arr[i]; 
            }
            else if (arr[i] > secondmax && arr[i] != max) 
                secondmax = arr[i]; 
        } 
          
        if (secondmax == INT_MIN) 
             cout<<"No second largest element in the array"; 
        else
             cout<<"The second largest element in the array is "<<secondmax; 
    }
int main()
{
    int arr[]={1,5,2,3,5,6,4,8};  
    int len=8;
    getnum(arr,len);
    return 0;
}

Output:

The second largest element in the array is 6.

Time Complexity: O(N)

This way we can enhance our code for improving efficiency.