Question

You are a given an array of n elements, design an algorithm to find the minimum element and the 2nd minimum element in the array using as few comparisons as possible.

For example, A[] can be [5, 6, 7, 3, 2, 1]. You should output 1 as minimum, 2 as 2nd minimum element in the array, and at the same time, minimize the number of comparisons used.


(i) describe the idea behind your algorithm in English
(ii) provide pseudocode
(iii) How many comparisons does your algorithm make?

Answer 1

Idea behind algorithm:
There is no way to find the second minimum element in array without knowing the minimum element because how can we know that an element is smaller than all rest elements in array except one(minimim), without knowing that one(minimum).
So, we have to find the minimum element, then and only we can find the second minimum.

Naive approach: 
find the minimum element in the array in one traversal
traverse the array once again, and find minimum element in array but not equal to the element we found in first traversal.
Efficient approach:
take two variables initially, i.e.  first, second.
now in single traversal of the array,
we can update the two variables in accordance with the current element of array we encounter in each iteration.
compare the current with first & second, and update first & second according to the outcome of comparison( this can be understood in Pseudocode below).


Pseudocode:
START
first = INT_MAX
second = INT_MAX
if len(arr) < 2:
   return "no second largest element exist"
for num in arr:
   if arr[i] < first:
      second = first
      first = arr[i]
   else if first <= arr[i] < second:     // if arr[i] is between first and second
      second = arr[i]
   return second
END;

Comparisons:

for every element in array, we have two if conditions,

so there are at most 2 comparisons for each element in array.

Let n be the number of elements in array.

So, total number of comparisons = 2*n