C: How to calculate second max from an array with least complexity?

Question

Say you are given two arrays where second array is duplicate with one missing element. What should be the best possible way to find that missing element -
array1: [1,2,3,4,5,6,7]
array2: [1,3,4,5,6,7]

Missing Element: 2

Answer 1

#include<stdio.h>
main()
{
    int a[5],i,j,temp;
    printf("Enter 5 integers\n");

    for(i=0;i<5;i++)
        scanf("%d",a+i);

    for(i=0;i<4;i++)
    {
        for(j=0;j<4-i;j++)
        {
            if(a[j]>a[j+1])
            {
            temp = a[j];
            a[j] = a[j+1];
            a[j+1] = temp;
            }
        }
    }

    printf("Second max number is %d\n",a[3]);
}

Answer 2

Try the following algo -
1) Take two variable first and second. Initialize both as INT_MIN (i.e. -infinity)
first = second = INT_MIN
2) Loop through all the elements.
a) If the current element is larger than first, then update first and second.
b) Else if the current element is larger than second then update second

At the end you will get second as second max.

Complexity: o(n)