Find second largest element in a array

algorithms

The problem is to solve it in n+logn−2 (base 2) no of comparisons.

My algorithm is taking some extra space less then (O(n*n)). How can i reduce this extra space without increasing the complexity.

    comparisionarray=[][] (2D array )

    //a function to find the largest.
    findlargest(a,b)
       if(len(a)==1 and  len(b)==1)
          append b to array at ath index in comparisonarray.
          append b to array at bth index comparisionarray.
          return max(a,b)
       else
          return max(findlargest(1stHalfof(a),2ndHalfof(a)),findlargest(1stHalfof(b),2ndHalfof(b))

    input= input_array()
    largest=findlargest(1stHalfof(input),2ndHalfof(input))
    subarray=[array at index largest in comparisionarray]
    2ndlargest=findlargest(1stHalfof(subarray),2ndHalfof(subarray))
    print(2ndlargest)

Edit: It can be done in minimum n+logn−2 comparisons. That is the only condition . This answer on math.stackexchange.com proves it. It has been generalized for nth largest element

Seems that there is a solution at this link stackoverflow. But i am not sure about the extra space and time complexity.

Best Answer

It looks like you're trying to do some sort of divide-and-conquer that you might find in a sorting algorithm. Sorting and taking the second value from the large end would work, but it's overkill for this problem because you don't really need to have the set of elements sorted when you're done.

The brute-force solution is O(n-1), does at most 2*(n-1) comparisons and occupies space equivalent to two of your set members:

l1 := first_member_in_set  -- Largest value
l2 := first_member_in_set  -- Second-largest value

for each set member m after the first
    if m > l1
        l2 := l1
        l1 := m
    else if m > l2
        l2 := m
    end if
end for

Note that for this to work (and for there to be a second-largest member at all), the set must have at least two members.

Related Topic