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

Data Nucleus Access Platform Note: This post is just my running notes and contains content consolidated from different sources while understanding datanucleus. DataNucleus (formerly known as Java Persistent Objects JPOX ) is an open source project (under the Apache 2 license) which provides a series of software products around data management in Java . DataNucleus Access Platform is a fully compliant implementation of the Java Data Objects (JDO) 1.0, 2.0, 2.1, 2.2, 3.0 specifications and the Java Persistence API 1.0, 2.0 specifications, providing transparent persistence of Java objects. It supports persistence to the widest range of datastores of any Java persistence software, supporting all of the main object-relational mapping (ORM) patterns, allows querying using either JDOQL , JPQL or SQL , and comes with its own byte-code enhancer. It allows persistence to relational datastores ( RDBMS ), object-based datastores ( db4o , NeoDatis ODB ), document-based storage( XML , Excel...
Post a Comment
Read more

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...
Post a Comment
Read more