Find Second largest element in an array

Given an array of integers, our task is to write a program that efficiently finds the second-largest element present in the array. 

Example:

Input: arr[] = {12, 35, 1, 10, 34, 1}
Output: The second largest element is 34.
Explanation: The largest element of the 
array is 35 and the second 
largest element is 34
Input: arr[] = {10, 5, 10}
Output: The second largest element is 5.
Explanation: The largest element of 
the array is 10 and the second 
largest element is 5
Input: arr[] = {10, 10, 10}
Output: The second largest does not exist.
Explanation: Largest element of the array 
is 10 there is no second largest element

Naive approach:

The idea is to sort the array in descending order and then return the second element which is not equal to the largest element from the sorted array.

Below is the implementation of the above idea:

The second largest element is 34

Complexity Analysis:

• Time Complexity: O(n log n). 
  The time required to sort the array is O(n log n).
• Auxiliary space: O(1). 
  As no extra space is required.

Much More Efficient and Easy to Understand:

   The Approach:

         Here,we use set for avoiding duplicates and we just return the second last element as we know set store in sorted order.

The Second Largest Element in Vector is: 34

Complexity Analysis:

Time Complexity: O(N log N). 
The Time Required To Insert Into Set And Traversing It O(N log N).
Auxiliary space: O(N). 
As Required For Set.

Efficient Approach: 

The approach is to traverse the array twice. In the first traversal find the maximum element.  In the second traversal find the greatest element in the remaining excluding the previous greatest.

Below is the implementation of the above idea:

Second largest : 34

Complexity Analysis:

• Time Complexity: O(n). 
  Two traversals of the array are needed.
• Auxiliary space: O(1). 
  As no extra space is required.

Efficient Approach: 

Find the second largest element in a single traversal. 

Below is the complete algorithm for doing this:  

1) Initialize the first as 0(i.e, index of arr[0] element
2) Start traversing the array from array[1],
   a) If the current element in array say arr[i] is greater
      than first. Then update first and second as,
      second = first
      first = arr[i]
   b) If the current element is in between first and second,
      then update second to store the value of current variable as
      second = arr[i]
3) Return the value stored in second.

Below is the implementation of the above approach:

The second largest element is 34

Complexity Analysis:

• Time Complexity: O(n). 
  Only one traversal of the array is needed.
• Auxiliary space: O(1). 
  As no extra space is required.

Another Approach for finding the second largest using the map data structure

Step 1: Initialize a map data.

Step 2: Store the elements of the array with their count in the map and map data structure always arrange the elements in their increasing order.

Step 3: If map size is greater than 1 then second largest exist else not exist.

Step 4: If size greater 1 then get the second last key from end by using rbegin() of map data structure because every key will be distinct. 

Step 5: Finally print the second largest. 

Let’s see the implementation for the above algorithm : –

The second largest element is: 34

Time Complexity: O(n), where n = size of array
Auxiliary Space: O(n)

Another Approach for finding the second largest element using the priority queue data structure

In C++ priority queue by default behaves like a max-heap. So in the priority queue, top element is the largest among all the elements that are present in that priority queue.

So here we will push all elements into a priority queue. Now its top element will be the largest element, so we will pop the top element. Now the element present at the top is the second largest element. So we will simply print that.

Code-

The Second Largest Element in Vector is: 34

Time Complexity: O(nlogn)
Auxiliary Space: O(n), for priority queue

Related Article: 
Smallest and second smallest element in an array

If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.