Skip to main content

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.

Comments

Post a Comment

Popular posts from this blog

Merge two sorted Lists or Arrays

Code to merge two array lists: public static ArrayList<Integer> mergeLists(ArrayList<Integer> l1 , ArrayList<Integer> l2 ){ ArrayList<Integer> l3 = new ArrayList<Integer>(); int i = 0; int j = 0; while ( i < ( l1 .size()) && j < ( l2 .size())){ if ( l1 .get( i ) < l2 .get( j )){ l3 .add( l1 .get( i )); i ++; } else { l3 .add( l2 .get( j )); j ++; } } if ( i < l1 .size()){ while ( i < l1 .size()){ l3 .add( l1 .get( i )); i ++; } } else if ( j < l2 .size()){ while ( j < l2 .size()){ l3 .add( l2 .get( j )); j ++; } } return l3 ; } Code to merge two arrays: public static int[] mergeArrays(int[] a, int[] b){ if((a == null || a.length == 0) && (b == null || b.length == 0)) return new int[0]; if((a == null || a.length == 0)) return b; if(b == n
Post a Comment
Read more

Binary search (recursive and non-recursive)

Recursive solution: public static int binarySearch( int [] array , int startIndex , int endIndex , int value ){ int midIndex = ( startIndex + endIndex )/2; if ( array [ midIndex ] == value ){ return value ; } if ( startIndex > endIndex ){ return -1; } if ( value < array [ midIndex ]){ int sI = startIndex ; int eI = midIndex - 1; return binarySearch( array , sI , eI , value ); } else { int sI = midIndex + 1; int eI = endIndex ; return binarySearch( array , sI , eI , value ); } } Non-Recursive solution: public static int binarySearchNoRecursion( int [] array ,  int value ){ int startIndex = 0; int endIndex = array . length - 1; while ( startIndex <= endIndex ){ int midIndex = ( startIndex + endIndex )/2; if ( array [ midIndex ] == value ){ return value ; } if ( value < ar
Post a Comment
Read more