Pages

Monday, June 11, 2012

Second largest element in an array

Given an unsorted array of size n, find the second largest element of the array in "n + log(n)" steps.
( Its not O(n+log(n)), its "n + log(n)" ).

Courtesy : Career cup.

5 comments:

Aakash said...

What exactly do you mean by a "step"? A comparison? A swap? An addition? A multiplication? Is more than one of these operations allowed in a single step?

Unknown said...

No. Only one of those operations is allowed in single step.

Unknown said...

Actually, a small change : More than one of these are allowed in single step. But no two operations in a step must be same.

Aakash said...

My Solution:
1. Construct a Max-heap in place. (N steps)
2. Delete the root. (log N steps)
3. Now, the root of the heap is the second-largest element.

Vinod Reddy G said...

I came across this puzzle before but in the version I saw it's number of comparisons that should be less than n+log(n).
If it's the case of comparisons then my solution :
let the array be A[0..n].Think of this as tournament.first 0 will play with 1,2 with 3,4 with 5 and so on.game between i and j will be won by i if A[i] > A[j].continue this process untill only one remains.The remaining one is largest and the second largest can only loose to the largest. so keep track of the list of numbers lost to a number.the maximum of the lost list of the final number gives the answer.
Of course the above solution only works when numbers are distinct(atleast the number of maximums is 1.