top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Find the second largest element in an integer array,without using sorting techniques and complexity must not exceed O(n)

+4 votes
790 views
Find the second largest element in an integer array,without using sorting techniques and complexity must not exceed O(n)
posted Mar 20, 2016 by Shahsikant Dwivedi

Share this question
Facebook Share Button Twitter Share Button LinkedIn Share Button

2 Answers

0 votes

Please find my answer as following:

Input - 13, 2, 41, 5 , 46, 7
first_big = 12 // first big
second_big = 2 // second big

for (i = 2; i < size - 1; i++)
{
if (arr[i] > first_big)
{
second_big = first_big;
first_big = arr[i];
}
}

First iteration:

second_big = 12
first_big = 41

Second iteration:

No change

Third iteration:

second_big = 41
first_big = 46

This is final result.
If someone has better logic to solve this problem then please share.

answer Mar 20, 2016 by Harshita
your logic can't be applied on any input i guess. output in:41 46 12 3 17 1 is first_big=41 and second_big=46  and output in 41 46 12 3 98 1 is first big=98,second big=41.in both cases output is wrong.please let me know if i understood your logic wrong, i guess u have taken the first and second integer of the array as first_big and second_big.
however slightly modified version works fine.
int main()
 {
     int arr[]={41,12,18,46,1};
     int second_big;
     int first_big=arr[0]>arr[1]?arr[0]:arr[1];
     if(first_big==arr[0])
        second_big=arr[1];
    else
        second_big=arr[0];
  for (i = 2; i < size ; i++)
    {
         if (arr[i] > first_big)
           {
             second_big = first_big;
             first_big = arr[i];
          }
  printf("%d",second_big);
}
  return 0;
 }
0 votes

Find the 2nd highest element:

int findSecondHighest(int *arr,int len){

     int max=0,second_highest,i;
     for(i=0;i<len;i++){
         if(max<arr[i]){
                    max=arr[i];
                    second_highest=max;
                 }
           }
      return second_highest;
}

Time Complexity=O(n)

answer Apr 4, 2016 by Amrutha Nk
Similar Questions
0 votes

Given an unordered array A of size n and integer x. What is the best complexity to find two elements in A whose sum is x?
Share the algo, its complexity and if possible C code.

+3 votes

In an "N" element integer sorted array, a particular elements is repeating "(N/2)+1" times. How much time it take to find the repeating element.

+2 votes

here is the sample code of problem :
a=100000000,b=200000;
multiplication=1;
while(a--){
multiplication=multiplication*b;
}
printf "multiplication= result"
reduce the time complexity by giving a suitable example which must have less complexity than this for large numbers.

...