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.


Aakash N S 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?

pathankhan salman said...

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

pathankhan salman 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 N S 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 Kumar 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 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.