Question

How to find second largest element in the array in O(N) time or O(NlogN) time ?

Answer 1

It can be done in O(N) time where 'N' is the size of array . 

First , we find the largest element of the array in one traversal , store the largest number's index . Say it is "x".

In the second traversal , we , again find the largest element , but ignore the element at position "x" . 

This way , we get the second largest element of the array . 

Code : 

#include <bits/stdc++.h>
using namespace std;

int main() 
{
    
     int n ; 
     cin>>n ; 
     int a[n] ; 
     int i = 0 ;
     while(i<n)
     {
         cin>>a[i];
         i++;
     }
     int max = -10000000;
     i=0;int x ; 
     while(i<n)
     {
         if(a[i]>max)
         {
             max = a[i] ; 
             x = i ; 
         }
         i++;
     }
     max = -10000000;
     i=0;
     while(i<n)
     {
         if(a[i]>max && i!=x)
         {
             max = a[i] ; 
         }
         i++;
     }
    
    cout<<max  ; 
    return 0;
}

 

Answer 2

1.we can use set in which all array elemets are inserted in sorted manner and then print the last element of set.

2. We can sort the array elements in decreasing order and then print the second array elements that is a[1].

Correct me if I am wrong.

Comments

You should also mention the time complexity of your solution :-)

---

If I am not wrong, the time and space complexities are as follows;
1. Time Complexity = O(N) and Space Complexity = O(N)
2. Time Complexity = O(N * logN) and Space Complexity = O(1)

---

You are correct , but space complexity should be O(N) in second case too , as we need to store elements in an array , before we sort the array :-)

Answer 3

Nlogn solution is simple just sort the array and give the second last element.

Now for O(n) solution taking two integers first and last initialize them both with INTMIN (smallest negative number in C++) . Now whenever an element comes which is greater than first , store the previous value of first in second and update the value of first and if the element is smaller than first check if its greater than second and if yes then update the value of second, in the end first will contain value of largest element and second will contain value of second largest element. Please see if you understand it, If not feel free to ask any doubt by pinging me on telegram