How can we find second maximum from array efficiently?
Posted
by Xinus
on Stack Overflow
See other posts from Stack Overflow
or by Xinus
Published on 2010-03-06T14:03:12Z
Indexed on
2010/04/21
9:23 UTC
Read the original article
Hit count: 172
Is it possible to find the second maximum number from an array of integers by traversing the array only once?
As an example, I have a array of five integers from which I want to find second maximum number. Here is an attempt I gave in the interview:
#define MIN -1
int main()
{
int max=MIN,second_max=MIN;
int arr[6]={0,1,2,3,4,5};
for(int i=0;i<5;i++){
cout<<"::"<<arr[i];
}
for(int i=0;i<5;i++){
if(arr[i]>max){
second_max=max;
max=arr[i];
}
}
cout<<endl<<"Second Max:"<<second_max;
int i;
cin>>i;
return 0;
}
The interviewer, however, came up with the test case int arr[6]={5,4,3,2,1,0};
, which prevents it from going to the if
condition the second time.
I said to the interviewer that the only way would be to parse the array two times (two for
loops). Does anybody have a better solution?
© Stack Overflow or respective owner