Get the Second Largest Number in a List in Linear Time

Get the second largest number in a list in linear time

Since @OscarLopez and I have different opinions on what the second largest means, I'll post the code according to my interpretation and in line with the first algorithm provided by the questioner.

def second_largest(numbers):
    count = 0
    m1 = m2 = float('-inf')
    for x in numbers:
        count += 1
        if x > m2:
            if x >= m1:
                m1, m2 = x, m1            
            else:
                m2 = x
    return m2 if count >= 2 else None

(Note: Negative infinity is used here instead of None since None has different sorting behavior in Python 2 and 3 – see Python - Find second smallest number; a check for the number of elements in numbers makes sure that negative infinity won't be returned when the actual answer is undefined.)

If the maximum occurs multiple times, it may be the second largest as well. Another thing about this approach is that it works correctly if there are less than two elements; then there is no second largest.

Running the same tests:

second_largest([20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7])
=> 74
second_largest([1,1,1,1,1,2])
=> 1
second_largest([2,2,2,2,2,1])
=> 2
second_largest([10,7,10])
=> 10
second_largest([1,1,1,1,1,1])
=> 1
second_largest([1])
=> None
second_largest([])
=> None

Update

I restructured the conditionals to drastically improve performance; almost by a 100% in my testing on random numbers. The reason for this is that in the original version, the elif was always evaluated in the likely event that the next number is not the largest in the list. In other words, for practically every number in the list, two comparisons were made, whereas one comparison mostly suffices – if the number is not larger than the second largest, it's not larger than the largest either.

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

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

Find second largest element in list with repeated elements

Here is an alternate method:

>>> a = [1.3, 2.1, 9999., 5., 3.7 ,6.6, 9999., 7.4, 9999., 3.5, 7, 1.2, 9999.]
>>> sorted(set(a))[-2]
7.4
>>>

And, believe it or not, it is actually quite a lot faster than the accepted solution:

>>> from timeit import timeit
>>> timeit("a=range(10000000);print sorted(set(a))[-2]", number=10)
9999998
9999998
9999998
9999998
9999998
9999998
9999998
9999998
9999998
9999998
34.327036257401424
>>> # This is NPE's answer
>>> timeit("a=range(10000000);maxa = max(a);print max(val for val in a if val != maxa)", number=10)
9999998
9999998
9999998
9999998
9999998
9999998
9999998
9999998
9999998
9999998
53.22811809880869
>>>

Above is a test that runs 10 times and works with a list that contains 10,000,000 items. Unless there is a flaw in my test (which I don't think there is), the solution I gave is clearly much faster.

Returning second highest element of a list using just a for loop and Len() method

You can use the following function -

def second_highest(nums):
    first = second = float('-inf')
    for x in nums:
        if first < x:
            second, first = first, x
        elif second < x:
            second = x
    return second

While traversing through the numbers -

1. if we come across a number that is greater than the max number seen so far, update max number and second-max number
2. else if we come across a number greater than second-max number but less than max number, update only the second-max number

>>> second_highest([1, 2, 3, 7, 9, 15, 4, 8 ])
9
>>> second_highest([15, 2, 3, 7, 9, 15, 4, 8 ])
15

The above is assuming len(nums) > 2 and second_highest([2, 2, 1]) -> 2, if you want it to be 1 instead, you can replace second elif condition with elif second < x and first != x.

Need to find second maximum number in the list. All the details pasted below in the body. Please assist

An easy implementation would be to do something like:

if len(set(input)) == 1:
   print('not present')
else:
   sorted(set(input))[-2]

Take a look at Get the second largest number in a list in linear time for other implementations.

---

Related Topics