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.
10
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.
I think the problem definition could use a bit of work.. Given the assumption that the data isn’t sorted I don’t see any reason why you can’t solve this in effectively 2n comparisons at most, with basically constant memory.. As you read the array you keep two variables. One holds the greatest value you’ve found so far the other keeps the second greatest. Every time you find a new maximum push the old one down to the second variable.
You want a http://en.m.wikipedia.org/wiki/Priority_queue of size 2. This easily generalizes to larger queues.
The usual implementation is an array form of a “heap” http://en.m.wikipedia.org/wiki/Heap_(data_structure) . (This is not a memory allocator kind of “heap”.)