An array of positive integers arr[ ] of size n , find the second largest element in the array . If the second largest element doesnot exist , return -1.
Examples :
Input : arr[] = [ 3 , 65, 55, 4, 9]
Output : 55
Explanation : The largest element of the array is 65 , and second largest element is 55
Input : arr[] =[4 , 4 , 4];
Output : -1
Approach 1:
Using Sorting
In this approach , we will sort the array elements in the increasing order . The largest element will be at index n-1 as in array index starts from 0.so, starting from index (n-2) , traverse the remaining array in reverse order . As soon as we found the element which is not equal to the largest element , return it as the second largest element as the array is already sorted in ascending order. If all the elements are equal to the largest element , return -1 .
import java.util.Arrays;
public class SecondLargestEle{
//Function to find the second largest element
public static int getSecondLargest(int [] arr ) {
int n=arr.length;
//Sort the array in ascending array
Arrays.sort(arr);
//Loop to find the second largest element, here start the loop from second last element as the last element is the largest element
for(int i=n-2 ; i>=0 ; i– ) {
//Now in this loop return the first element which is not equal to the largest element, as the array is already sorted in ascending order , so while iterating from last index in reverse order, the first element you find which is not equal to the largest will be the second largest element .
if ( arr [i ]!=arr[n-1] ) {
return arr[ i ];
}
}
// If the second largest element is not found return -1
return -1;
}
public static void main (String args[] ) {
int arr[]= {3 , 8 , 65, 88, 9, 19};
System.out.println(“Second largest element is : “+getSecondLargest(arr));
}
}
OUTPUT :
Second largest element is : 65
Approach2 :
Two Pass Search
In this approach , traverse the array twice . In the first traversal , find the maximum element . In the second traversal , find the the maximum element ignoring the one found in the first traversal .
import java.util.Arrays;
public class SecondLargestEle{
//Function to find the second largest element in the array
public static int getSecondLargest(int arr[] ) {
int n= arr.length;
int largest=-1;
int secondLargest=-1;
// Finding the largest element
for ( int i=0 ; i<n; i++ ) {
if ( arr[i ] >largest ) {
largest=arr[i];
}
// Finding the second largest element
for ( int i= 0 ; i< n ; i++){
// If the current element is greater than the secondLargestElement and not equal to the largest element , then update the second largest Element .
if ( arr[i] > secondLargest && arr[i] ! = largest ) {
secondLargest= arr[i] ;
}
}
return secondLargest;
}
public static void main (String args[] ) {
int arr[ ] = { 3, 7, 88, 99,65,9};
System.out.println(getSecondLargest(arr));
}
}
OUTPUT :
88