Find the 2nd largest element in an array with minimum number of comparisons

by

The optimal algorithm uses n+log n-2 comparisons. Think of elements as competitors, and a tournament is going to rank them.

First, compare the elements, as in the tree

   |
  / \
 |   |
/ \ / \
x x x x

this takes n-1 comparisons and each element is involved in comparison at most log n times. You will find the largest element as the winner.

The second largest element must have lost a match to the winner (he can’t lose a match to a different element), so he’s one of the log n elements the winner has played against. You can find which of them using log n – 1 comparisons.

The optimality is proved via adversary argument. See https://math.stackexchange.com/questions/1601 or http://compgeom.cs.uiuc.edu/~jeffe/teaching/497/02-selection.pdf or http://www.imada.sdu.dk/~jbj/DM19/lb06.pdf or https://www.utdallas.edu/~chandra/documents/6363/lbd.pdf

More Related Contents:

  1. maximize the top element of the stack after performing exactly K operations
  2. Algorithm for all subsets of Array
  3. How to sort in-place using the merge sort algorithm?
  4. Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing
  5. Finding three elements in an array whose sum is closest to a given number
  6. Given an array of numbers, return array of products of all other numbers (no division)
  7. How to find the kth smallest element in the union of two sorted arrays?
  8. Algorithm to find k smallest numbers in array of n items
  9. How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N [duplicate]
  10. Can min/max of moving window achieve in O(N)?
  11. Weighted random selection from array
  12. Print two-dimensional array in spiral order
  13. Find the Smallest Integer Not in a List
  14. Binary Search in Array
  15. Find the majority element in array
  16. How to divide a set into two subsets such that difference between the sum of numbers in two sets is minimal?
  17. Given an array, find out the next smaller element for each element
  18. mongodb find by multiple array items
  19. Algorithm to determine if array contains n…n+m?
  20. Find all subsets of length k in an array
  21. Maximum single-sell profit
  22. In-place array reordering?
  23. find pair of numbers in array that add to given sum
  24. Regarding in-place merge in an array
  25. Check if an element is present in a Bash array [duplicate]
  26. Interview question: three arrays and O(N*N)
  27. Maximum sum of non consecutive elements
  28. calculating the number of “inversions” in a permutation
  29. Algorithm to apply permutation in constant memory space
  30. Find the first element in a sorted array that is greater than the target

Leave a Comment