Codeanu - 7 months ago 43
C Question

# Traversing an array to find the second largest element in linear time

Is there a way in linear time by which we can find which is the second largest element of an array ?
Array elements can be positive, negative or zero.
Elements can be repetitive.
No STLs allowed.
Python can be used.

Solution : Sort the array and take the second element but Sorting not allowed

Modification : By definition second largest element will be the one which is numerically smaller. Like if we have

Arr = {5,5,4,3,1}
Then second largest is 4

Addition
Lets say if i want to generalize the question to kth largest and complexity less than linear like nlogn, what can be the solution.

Answer

If you want a true O(n) algorithm, and want to find nth largest element in array then you should use quickselect (it's basically quicksort where you throw out the partition that you're not interested in), and the below is a great writeup, with the runtime analysis:

http://pine.cs.yale.edu/pinewiki/QuickSelect