Find Second largest Element in an Array

Find Second largest Element in an Array in Minimum Time Complexity

1. State different ways and the Complexities involved with them

• Keep two pointers, largest, second_largest. Let the first element is largest and second element as second_largest. Compare. After comparison, largest, second_largest will point to right array indices. Move from the third index till the end of array. At each entry to loop, again compare and reset the pointers: largest and second_largest. This solution is of order n, o(n) as there are almost 2n comparisons

A general variation of this problem will be to find out the kth largest in an array of N numbers

• Kth largest logically means that in a set of K elements , find the smallest element. This smallest in the set of K elements is the Kth largest for the set of K. So steps include

Using Min-heap

• Get the first K elements. Construct a min-heap of it. Order of Complexity of constructing this heap = kLog(k)
• Root of this min-heap, which is the smallest of this heap, is the currently the kth largest on this set of k
• a: Iterate over the array from k+1 index. Get the k+1 element of array. If it is less, ignore it
• b: If k+1 th element is greater then root, then insert this element in the min-heap. Order of Complexity for this Log(k)
• c: Remove the smallest , which is the new root. order of Complexity for this is again Log(k)
• d: Now the min-heap again contains K elements, the new root is now the K th largest.
• Do the steps a, b, c, d, for the rest of the elements of array

Order of Complexity in this case:

Order of Complexity to construct the min-heap of K elements = kLog(k)- one time

order of Complexity to insert a new element = kLog(k) - ( n-k) times

order of Complexity to remove the root = kLog(k) - ( n-k) times

Total complexity, order :

kLog(k) + 2*(n-k)*Log(k)