Friday, June 28, 2013

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)

No comments:

Post a Comment