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

Reentrant Locks

Synchronized uses intrinsic locks or monitors. Every object in Java has an intrinsic lock associated with it. Whenever a thread tries to access a synchronized block or method, it acquires the intrinsic lock or the monitor on that object. In the case of static methods, the thread acquires the lock over the class object. ReentrantLock is an explicit locking mechanism.  A reentrant mutual exclusion Lock with the same basic behavior and semantics as the implicit monitor lock accessed using synchronized methods and statements, but with following extended capabilities. Polled and Timed Lock Acquisition Lock.tryLock() is polled lock acquisition mechanism and tryLock(long timeout, TimeUnit unit) is timed lock acquisition mechanism. tryLock() will return immediately. If no other thread locked, then it will return true else returns false. The tryLock(long timeout, TimeUnit unit) will wait for the timeout period to acquire the lock if the lock is not available until timeou...

Useful Java Related Resources

Java Tech Videos: http://www.techonvideo.com/category/programming/java/ Java Annotations: http://www.developer.com/java/other/article.php/3556176/An-Introduction-to-Java-Annotations.htm http://download.oracle.com/javase/tutorial/java/javaOO/annotations.html