Friday, January 21, 2011

Find the second largest number in an array

Given an array of integers find the value of 2nd largest element in minimum number of comparisons.

Approach

Well its trivial to prove that the lower bound of the algorithm will be O(n) (Since the array is unordered so we need to scan the values atleast once to figure out the solution)

What can be the possible solutions?




Well simplest is to sort the array and then return the 2nd last element from the array.

But do we really need to sort? Lets say you needed to find the highest element do you still need to sort? Well only one scan of the array would have the answer, with (n -1) comparisons.
So to calculate the 2nd highest number would take another n - 2 comparisons to figure out the second highest elements. So total comparisons are 2n - 3 i.e O(n) algorithm.

As stated earlier the O(n) is an optimal order and we cannot get better than that, but can we reduce the constant coefficients of the order, in other words can we reduce the number of comparisons?

Lets relate this to a real life situation where you have N teams, and you wish to have two best finalist, will you go ahead with the same order of comparisons?

Well absolutely not, we all know how the tournaments are set up, can we use the same principles here and check if it works out and yet efficiently.

The below picture speaks more than anything,



Well now the highest element is undoubtedly 9, but how about the 2nd highest element, it has to be among the ones which has been defeated by 9, and those are 8, 3, 7

In nutshell there will be logn elements among which the highest element can be found in logn -1 comparisons. So the overall comparisons reduces to n - 2 + logn which is definetly better than 2n -3


11 comments :

  1. Sir
    Minimum number of comparisons will be (n-1) +(log n -1)
    n-1 for maximum element and (log n ) -1 is for second maximum element.
    Abhishek Prajapati
    NIT jsr

    ReplyDelete
  2. @abhishek ... yeah but i think it should be (n-1)+log(n) ..can u share ur approach or method also....

    ReplyDelete
  3. @aviral sir
    i have considered binary tree approach we have do exactly n-1 comparisons to find the max element now the max. element at each level of the binary tree wins the comparison so there would have been (log n)levels
    in the tree so the second max. element fall among these elements now to compute the 2 nd max. we can compute the max. element of the array which consists these log(n) elements which can be done in log(n)-1 ways ............

    ReplyDelete
  4. @abhishek .. nice one... more commonly this approach is known as tournament algorithm
    Regards

    ReplyDelete
  5. Abhishek PrajapatiJanuary 23, 2011 at 1:02 AM

    @aviral sir
    thanxs sir

    ReplyDelete
  6. Split the array in two parts as in quick sort using pivot element where left contains smaller and right contains larger element.
    Recursively split the right part till it contains only 1 elements.
    Now pivot is the 2nd largest number in the array

    Is it better then binary tree approach ?

    ReplyDelete
  7. yeah binary tree approach is better as in quick sort modification ur worst case boils down to O(n^2).... you can have a look for finding other similar algorithms in selection algorithm
    http://en.wikipedia.org/wiki/Selection_algorithm

    ReplyDelete
  8. guys you have to solve this O(n) and there is solution to this problem...

    take two variable and save the largest in variable and second largest in the second one.. scan through the array... and finally you have second largest element... :).. it's that simple and it is the Adobe written question on dec. 2010...

    happy coding.
    abhijeet

    ReplyDelete
  9. @abhijeet ... ur solution takes a total of 2*n-3 comparisons.. while the method suggested by abhishek(tournament principle) takes the only (n-1)+logn steps which is surely more optimised than yours.

    Regards

    ReplyDelete
  10. but,the tree approach requires another auxillary space O(n)

    ReplyDelete
  11. you don't need to construct the tree itself(which would cost you nlogn in creation itself). The formation of tree is via the recursion (something like merge sort and D&C).
    You can read more on
    http://en.wikipedia.org/wiki/Selection_algorithm#Tournament_Algorithm

    Regards

    ReplyDelete