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

129 views
C: How to calculate second max from an array with least complexity? posted Jan 16, 2015

#include<stdio.h>
main()
{
int a,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);
} answer Jan 19, 2015

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) answer Jan 19, 2015
Similar Questions
–1 vote

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