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

Question

For an array of size N  what is the number of comparisons required

User · Accepted Answer

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

User · Answer

class solution  def SecondLargestNumber  self l       Largest   0     secondLargest   0     for i in l          if i gt  Largest              secondLargest   Largest         Largest   max Largest  i      return Largest  secondLargest

User · Answer

Use Bubble sort or Selection sort algorithm which sorts the array in descending order  Don t sort the array completely  Just two passes  First pass gives the largest element and second pass will give you the second largest element   No  of comparisons for first pass  n-1  No  of comparisons for first pass  n-2  Total no  of comparison for finding second largest  2n-3  May be you can generalize this algorithm  If you need the 3rd largest then you make 3 passes   By above strategy you don t need any temporary variables as Bubble sort and Selection sort are in place sorting algorithms

User · Answer

Use counting sort and then find the second largest element  starting from index 0 towards the end  There should be  at least 1 comparison  at most n-1  when there s only one element

User · Answer

case 1-- 9 8 7 6 5 4 3 2 1 case 2--  50 10 8 25          case 3--  50 50 10 8 25          case 4--  50 50 10 8 50 25           public void second element             int a 10  i max1 max2          max1 a 0  max2 a 1           for i 1 i lt a length   i                         if a i  gt max1                             max2 max1                 max1 a i                            else if a i  gt max2  amp  amp a i   max1               max2 a i              else if max1  max2               max2 a i

User · Answer

function findSecondLargeNumber arr        var fLargeNum   0      var sLargeNum   0       for var i 0  i lt arr length  i             if fLargeNum  lt  arr i                sLargeNum   fLargeNum              fLargeNum   arr i                     else if sLargeNum  lt  arr i                sLargeNum   arr i                        return sLargeNum     var myArray    799  -85  8  -1  6  4  3  -2  -15  0  207  75  785  122  17     Ref  http   www ajaybadgujar com finding-second-largest-number-from-array-in-javascript

User · Answer

The accepted solution by sdcvvc in C  11    include  lt algorithm gt   include  lt iostream gt   include  lt vector gt   include  lt cassert gt   include  lt climits gt   using std  vector  using std  cout  using std  endl  using std  random shuffle  using std  min  using std  max   vector lt int gt  create tournament const vector lt int gt  amp  input         make sure we have at least two elements  so the problem is interesting   if  input size    lt   1        return input         vector lt int gt  result 2   input size   - 1  -1      int i   0    for  const auto amp  el   input        result input size   - 1   i    el        i         for  uint j   input size     2  j  gt  0  j  gt  gt   1        for  uint k   0  k  lt  2   j  k    2          result j - 1   k   2    min result 2   j - 1   k   result 2   j   k                 return result     int second smaller const vector lt int gt  amp  tournament      const auto amp  minimum   tournament 0     int second   INT MAX     for  uint j   0  j  lt  tournament size     2          if  tournament 2   j   1     minimum          second   min second  tournament 2   j   2          j   2   j   1            else         second   min second  tournament 2   j   1          j   2   j   2               return second     void print vector const vector lt int gt  amp  v      for  const auto amp  el   v        cout  lt  lt  el  lt  lt             cout  lt  lt  endl     int main        vector lt int gt  a    for  int i   1  i  lt   2048    i      a push back i      for  int i   0  i  lt  1000  i          random shuffle a begin    a end         const auto amp  v   create tournament a       assert  second smaller v     2          return 0

User · Answer

I have gone through all the posts above but I am convinced that the implementation of the Tournament algorithm is the best approach  Let us consider the following algorithm posted by  Gumbo  largest    numbers 0   secondLargest    null for i 1 to numbers length-1 do     number    numbers i       if number  gt  largest then         secondLargest    largest          largest    number      else         if number  gt  secondLargest then             secondLargest    number          end      end  end    It is very good in case we are going to find the second largest number in an array  It has  2n-1  number of comparisons  But what if you want to calculate the third largest number  or some kth largest number  The above algorithm doesn t work  You got to another procedure    So  I believe tournament algorithm approach is the best and here is the link for that

User · Answer

You can find the second largest value with at most 2   N-1  comparisons and two variables that hold the largest and second largest value   largest    numbers 0   secondLargest    null for i 1 to numbers length-1 do     number    numbers i       if number  gt  largest then         secondLargest    largest          largest    number      else         if number  gt  secondLargest then             secondLargest    number          end      end  end

User · Answer

int   int array    4  6  2  9  1  7  4  2  9  0  3  6  1  6  8       int largst int array 0       int second int array 0       for  int i 0  i lt int array length  i                     if int array i  gt largst                 second largst              largst int array i                       else if int array i  gt second   amp  amp   int array i  lt largst                 second int array i

User · Answer

It can be done in n   ceil log n  - 2 comparison   Solution  it takes n-1 comparisons to get minimum   But to get minimum we will build a tournament in which each element will be grouped in pairs  like a tennis tournament and winner of any round will go forward   Height of this tree will be log n since we half at each round   Idea to get second minimum is that it will be beaten by minimum candidate in one of previous round  So  we need to find minimum in potential candidates  beaten by minimum    Potential candidates will be log n   height of tree  So  no  of comparison to find minimum using tournament tree is n-1 and for second minimum is log n -1 sums up   n   ceil log n  - 2  Here is C   code   include  lt iostream gt   include  lt cstdio gt   include  lt cstdlib gt   include  lt cmath gt   include  lt vector gt   using namespace std   typedef pair lt int int gt  ii   bool isPowerOfTwo  int x         First x in the below expression is for the case when x is 0      return x  amp  amp     x amp  x-1          modified int log 2 unsigned int n        int bits   0      if   isPowerOfTwo n           bits        if  n  gt  32767            n  gt  gt   16          bits    16            if  n  gt  127            n  gt  gt   8          bits    8            if  n  gt  7            n  gt  gt   4          bits    4            if  n  gt  1            n  gt  gt   2          bits    2            if  n  gt  0            bits              return bits     int second minima int a    unsigned int n            build a tree of size of log2n in the form of 2d array        1st row represents all elements which fights for min        candidate pairwise  winner of each pair moves to 2nd        row and so on     int log 2n   log 2 n       long comparison count   0         pair of ints   first element stores value and second                       stores index of its first row     ii   p   new ii  log 2n       int i  j  k      for  i   0  j   n  i  lt  log 2n  i              p i    new ii j           j   j amp 1   j 2 1   j 2            for  i   0  i  lt  n  i            p 0  i    make pair a i   i             find minima using pair wise fighting     for  i   1  j   n  i  lt  log 2n  i                 for each pair         for  k   0  k 1  lt  j  k    2                   find its winner             if    comparison count  amp  amp  p i-1  k  first  lt  p i-1  k 1  first                    p i  k 2  first   p i-1  k  first                  p i  k 2  second   p i-1  k  second                            else                   p i  k 2  first   p i-1  k 1  first                  p i  k 2  second   p i-1  k 1  second                                      if no  of elements in row is odd the last element            directly moves to next round  row          if  j amp 1                p i  j 2  first   p i-1  j-1  first              p i  j 2  second   p i-1  j-1  second                    j   j amp 1   j 2 1   j 2               int minima  second minima      int index      minima   p log 2n-1  0  first         initialize second minima by its final  last 2nd row         potential candidate with which its final took place     second minima   minima    p log 2n-2  0  first   p log 2n-2  1  first   p log 2n-2  0  first         minima original index     index   p log 2n-1  0  second      for  i   0  j   n  i  lt   log 2n - 3  i                 if its last candidate in any round then there is            no potential candidate         if  j amp 1  amp  amp  index    j-1                index    2              j   j 2 1              continue                       if minima index is odd  then it fighted with its index - 1            else its index   1            this is a potential candidate for second minima  so check it         if  index amp 1                if    comparison count  amp  amp  second minima  gt  p i  index-1  first                  second minima   p i  index-1  first                    else               if    comparison count  amp  amp  second minima  gt  p i  index 1  first                  second minima   p i  index 1  first                    index  2          j   j amp 1   j 2 1   j 2              printf  ------------------------------------------------------------------------------- n        printf  Minimum             d n   minima       printf  Second Minimum      d n   second minima       printf  comparison count    ld n   comparison count       printf  Least No  Of Comparisons          printf  n ceil log2 n -2     d n    int  n ceil log n  log 2  -2        return 0     int main         unsigned int n      scanf   u    amp n       int a n       int i      for  i   0  i  lt  n  i            scanf   d    amp a i        second minima a n       return 0

User · Answer

include lt stdio h gt  main             int a 5     55 11 66 77 72           int max min i          int smax smin          max   min   a 0           smax   smin   a 0           for i 0 i lt  4 i                              if a i  gt max                                            smax   max                          max   a i                                     if max gt a i  amp  amp smax lt a i                                             smax   a i                                       printf  the first max element z  d n  max           printf  the second max element z  d n  smax

User · Answer

Here is some code that might not be optimal but at least actually finds the 2nd largest element   if  val  0    gt  val  1           largest   val  0       secondLargest   val  1      else       largest   val  1       secondLargest   val  0       for  i   2  i  lt  N    i         if  val  i    gt  secondLargest                 if  val  i    gt  largest                         secondLargest   largest              largest   val  i                      else                       secondLargest   val  i                        It needs at least N-1 comparisons if the largest 2 elements are at the beginning of the array and at most 2N-3 in the worst case  one of the first 2 elements is the smallest in the array

User · Answer

Suppose provided array is  inPutArray    1 2 5 8 7 3  expected O P -  7  second largest    take temp array        temp    0 0   int dummmy 0      for  no in inPutArray        if temp 1  lt no       temp 1    no      if temp 0  lt temp 1        dummmy   temp 0      temp 0    temp 1      temp 1    temp                    print  Second largest no is  d  temp 1

User · Answer

A good way with O 1  time complexity would be to use a max-heap  Call the heapify twice and you have the answer

User · Answer

Assuming space is irrelevant  this is the smallest I could get it  It requires 2 n comparisons in worst case  and n comparisons in best case   arr     0  12  13  4  5  32  8   max     -1  -1    for i in range len arr         if  arr i   gt  max 0             max insert 0 arr i        elif  arr i   gt  max 1             max insert 1 arr i    print max 1

User · Answer

I know this is an old question  but here is my attempt at solving it  making use of the Tournament Algorithm  It is similar to the solution used by  sdcvvc   but I am using two-dimensional array to store elements   To make things work  there are two assumptions  1  number of elements in the array is the power of 2 2  there are no duplicates in the array  The whole process consists of two steps   1  building a 2D array by comparing two by two elements  First row in the 2D array is gonna be the entire input array  Next row contains results of the comparisons of the previous row  We continue comparisons on the newly built array and keep building the 2D array until an array of only one element  the largest one  is reached   2  we have a 2D-array where last row contains only one element  the largest one  We continue going from the bottom to the top  in each array finding the element that was  beaten  by the largest and comparing it to the current  second largest  value  To find the element beaten by the largest  and to avoid O n  comparisons  we must store the index of the largest element in the previous row  That way we can easily check the adjacent elements  At any level  above root level  the adjacent elements are obtained as   leftAdjacent   rootIndex 2 rightAdjacent   rootIndex 2 1    where rootIndex is index of the largest root  element at the previous level   I know the question asks for C    but here is my attempt at solving it in Java   I ve used lists instead of arrays  to avoid messy changing of the array size and or unnecessary array size calculations   public static Integer findSecondLargest List lt Integer gt  list            if  list    null                return null                    if  list size      1                return list get 0                     List lt List lt Integer gt  gt  structure   buildUpStructure list           System out println structure           return secondLargest structure               public static List lt List lt Integer gt  gt  buildUpStructure List lt Integer gt  list            List lt List lt Integer gt  gt  newList   new ArrayList lt List lt Integer gt  gt             List lt Integer gt  tmpList   new ArrayList lt Integer gt  list           newList add tmpList           int n   list size            while  n gt 1                tmpList   new ArrayList lt Integer gt                 for  int i   0  i lt n  i i 2                    Integer i1   list get i                   Integer i2   list get i 1                   tmpList add Math max i1  i2                              n   2              newList add tmpList                  list   tmpList                    return newList             public static Integer secondLargest List lt List lt Integer gt  gt  structure            int n   structure size            int rootIndex   0          Integer largest   structure get n-1  get rootIndex           List lt Integer gt  tmpList   structure get n-2           Integer secondLargest   Integer MIN VALUE          Integer leftAdjacent   -1          Integer rightAdjacent   -1          for  int i   n-2  i gt  0  i--                rootIndex  2              tmpList   structure get i               leftAdjacent   tmpList get rootIndex               rightAdjacent   tmpList get rootIndex 1                if  leftAdjacent equals largest                     if  rightAdjacent  gt  secondLargest                        secondLargest   rightAdjacent                                              if  rightAdjacent equals largest                     if  leftAdjacent  gt  secondLargest                        secondLargest   leftAdjacent                                    rootIndex rootIndex 1                                   return secondLargest

User · Answer

I suppose  follow the  optimal algorithm uses n log n-2 comparisons  from above  the code that I came up with that doesn t use binary tree to store the value would be the following   During each recursive call  the array size is cut in half   So the number of comparison is    1st iteration  n 2 comparisons  2nd iteration  n 4 comparisons  3rd iteration  n 8 comparisons      Up to log n iterations   Hence  total    n - 1 comparisons   function findSecondLargestInArray array        let winner           if  array length     2            if  array 0   lt  array 1                 return array 0             else               return array 1                       for  let i   1  i  lt   Math floor array length   2   i              if  array 2   i - 1   gt  array 2   i - 2                 winner push array 2   i - 1              else               winner push array 2   i - 2                        return findSecondLargestInArray winner       Assuming array contain 2 n number of numbers   If there are 6 numbers  then 3 numbers will move to the next level  which is not right   Need like 8 numbers    4 number    2 number    1 number    2 n number of number

User · Answer

PHP version of the Gumbo algorithm  http   sandbox onlinephpfunctions com code 51e1b05dac2e648fd13e0b60f44a2abe1e4a8689   numbers    10  9  2  3  4  5  6  7     largest    numbers 0    secondLargest   null  for   i 1   i  lt  count  numbers    i           number    numbers  i       if   number  gt   largest             secondLargest    largest           largest    number        else if   number  gt   secondLargest             secondLargest    number           echo  largest  largest  secondLargest  secondLargest

User · Answer

package com array orderstatistics   import java util Arrays  import java util Collections   public class SecondLargestElement                    Total Time Complexity will be n log n   O 1          param str             public static void main String str              Integer   integerArr   new Integer     5  1  2  6  4                  Step1   Time Complexity will be n log n          Arrays sort integerArr  Collections reverseOrder                 Step2   Array get Second largestElement         int secondLargestElement   integerArr 1            System out println secondLargestElement

User · Answer

Sorry  JS code     Tested with the two inputs   a    55 11 66 77 72   a     0  12  13  4  5  32  8     var first   Number MIN VALUE  var second   Number MIN VALUE  for  var i   -1  len   a length    i  lt  len         var dist   a i          get the largest 2     if  dist  gt  first            second   first          first   dist        else if  dist  gt  second        amp  amp  dist  lt  first       this is actually not needed  I believe         second   dist           console log  largest  second largest  first second   largest  second largest 32 13   This should have a maximum of a length 2 comparisons and only goes through the list once

User · Answer

The following solution would take 2 N-1  comparisons   arr   array with  n  elements first arr 0  second -999999   large negative no i 1 while i is less than length arr       if arr i  greater than first          second first         first arr i      else          if arr i  is greater than second and arr i  less than first              second arr i      i i 1 print second

User · Answer

try this   max1   a 0   max2  for i   0  until length    if a i   gt  max       max2   max1       max1   a i         end IF    end FOR return min2    it should work like a charm  low in complexity   here is a java code   int secondlLargestValue int   secondMax   int max1   secondMax 0      assign the first element of the array  no matter what  sorted or not  int max2   0     anything really work  but zero is just fundamental     for int n   0  n  lt  secondMax length  n        start at zero  end when larger than length  grow by 1           if secondMax n   gt  max1      nth element of the array is larger than max1  if so             max2   max1     largest in now second largest             max1   secondMax n      and this nth element is now max             end IF        end FOR     return max2     end secondLargestValue

User · Answer

Sort the array into ascending order then assign a variable to the  n-1 th term

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

Examples related to arrays

Examples related to algorithm

Examples related to search