Find second largest element in an array

Find second largest element in an unsorted array.

            

We can reach the solution in three ways. 

Solution 1

Sort the array and return last but one element. We could use already existing sorting methods in JDK Arrays class and sort the array.

public static int findSecondLargestV1(int[] array){

if(array.length == 0 || array.length < 2){

return -1;

}

Arrays.sort(array);

return array[array.length - 2];

}

Complexity: Since this solution depends on sorting, the complexity is equal to complexity of sorting algorithm, ie., O(n log n)

Solution 2

public static int findSecondLargestV2(int[] array){

if(array.length == 0 || array.length < 2){

return -1;

}

int max = -1;

for(int i = 0; i < array.length; i++){

if(array[i] > max){

max = array[i];

}

}

int secondMax = -1;

for(int i = 0; i < array.length ; i++){

if(array[i] > secondMax && array[i] < max){

secondMax = array[i];

}

}

return secondMax;

}

Complexity: O(2n) that is O(n)

Solution 3

public static int findSecondMax(int[] array){
if(array == null || array.length == 0){
return -1;
}

int maxIndex = 0;
int secMaxIndex = -1;

for(int i = 1; i < array.length ; i++){
if(array[i] > array[maxIndex]){
secMaxIndex = maxIndex;
maxIndex = i;
}

if(secMaxIndex == -1 && array[i] < array[maxIndex]){
secMaxIndex = i;
}else if(array[i] < array[maxIndex] && array[i] > array[secMaxIndex]){
secMaxIndex = i;
}
}
return secMaxIndex;
}

Complexity: O(n)

Similar approaches can be used to find the second smallest element in an unsorted array by just reversing the conditions above.