10. Find second largest element

Given an array of elements. Your task is to find the second maximum element in the array. If there does not exist any second largest element, then return -1. Array contains duplicates

Example 1:
Input:
N=5
arr[] = { 2, 4, 5, 6, 7 }
Output:  6
Explanation:
The largest element is 7 and 
the second largest element is 6.

Example 2:
Input:
N=6
arr[] = { 7, 8, 2, 1, 4, 3 }
Output:  7

Solution: (Two Traversal)

Approach: Find the maximum element Find the second maximum which is not equal to maximum

class Solution
{
public:
    int print2largest(int arr[], int arr_size)
    {

        int mx = INT_MIN;
        for (int i = 0; i < arr_size; i++)
        {
            if (arr[i] > mx)
            {
                mx = arr[i];
            }
        }

        int mx2 = INT_MIN;
        for (int i = 0; i < arr_size; i++)
        {
            if (arr[i] < mx && arr[i] > mx2)
            {
                mx2 = arr[i];
            }
        }

        if (mx2 == INT_MIN)
        {
            return -1;
        }
        return mx2;
    }
};

Time Complexity: O(n)

Solution: (Using one traversal)

Use two variables max and second max If value is greater than max: second max = max max = value If value lies in between: second max = value

class Solution
{
public:
    int print2largest(int arr[], int arr_size)
    {
        int max = arr[0];
        int sec_max = INT_MIN;

        for (int i = 1; i < arr_size; i++)
        {
            if (arr[i] > max)
            {
                sec_max = max;
                max = arr[i];
            }
            else if (arr[i] > sec_max && arr[i] < max)
            {
                sec_max = arr[i];
            }
        }

        if (sec_max == INT_MIN)
        {
            return -1;
        }
        return sec_max;
    }
};

Time Complexity: O(n)