Second Minimum Element

Find second smallest element in an array A[1..N] of size N. (We would like to do in much less than 2N comparisons if possible).

Solution :

Finding the smallest element is trivial. The following code would find the smallest element using n-1 comparisons.

min = A[1]
for i = 2 to n
  if A[i] < min 
    min = A[i]
return min

The trivial algorithm to find the second minimum is to keep another variable (smin) along with min and if an element knocks out smin then check if it knocks out min and accordingly do the book-keeping. It can be done using 2n-3 comparisons and takes constant space. 

A point to observe is that the second smallest element is knocked out by the smallest one at some stage. If we preserve which element is knocked out by whom then finding the second smallest element would just require us to find the smallest amongst the elements knocked out by the smallest element.

But in order to do that we need to build the algorithm in a way that we are playing a pair wise tournament. Lets say we play a tournament and knockout n/2 elements after n/2 comparisons. The recurrence relation looks like this: 

T(n) = T(n/2) + n/2

Solving this recurrence gives that T(n) = n - 1. The height of the recurrence tree is lg n. So if we just check these elements knocked by root (min) we get the second minimum.For. E.x.

1   5 2   6  
\ /   \ /  
 1     2
  \   /
    1

As soon as we build the tree using n-1 comparisons, we can check the second largest amongst the number knocked out by 1. i.e. 2, 5. so the second minimum is 2. 

This algorithm can be implemented using an auxiliary array B[1..n]. This tree represents a min heap and can be stored in an array easily. There are many divisions performed (ideally they are right shifts) to index the correct elements, so the actual implementation might look a little complicated.

Another algorithm that is very easy to implement but sadly takes 2n - 2logn - 1 in terms of array element comparisons. Simply build a min heap (rooted at 1). Return the smaller of numbers at index 2 or 3 in the array. The cost of min heap building is = 2 * [n/4 + 2n/8 + ...... + (logn - 1) * n / 2^logn]. The solution to this arithmetic - geometric series is 2n - 2logn - 2. Comparing elements at 2nd and 3rd index adds one to the cost. Its very easy to implement though

Acknowledgments :

http://n1b-algo.blogspot.com/2008/12/finding-second-smallest-element.html