How can we find second maximum from array efficiently?
- by Xinus
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?
