[python] Get the second largest number in a list in linear time

I'm learning Python and the simple ways to handle lists is presented as an advantage. Sometimes it is, but look at this:

>>> numbers = [20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7]
>>> numbers.remove(max(numbers))
>>> max(numbers)
74

A very easy, quick way of obtaining the second largest number from a list. Except that the easy list processing helps write a program that runs through the list twice over, to find the largest and then the 2nd largest. It's also destructive - I need two copies of the data if I wanted to keep the original. We need:

>>> numbers = [20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7]
>>> if numbers[0]>numbers[1]):
...    m, m2 = numbers[0], numbers[1]
... else:
...    m, m2 = numbers[1], numbers[0]
...
>>> for x in numbers[2:]:
...    if x>m2:
...       if x>m:
...          m2, m = m, x
...       else:
...          m2 = x
...
>>> m2
74

Which runs through the list just once, but isn't terse and clear like the previous solution.

So: is there a way, in cases like this, to have both? The clarity of the first version, but the single run through of the second?

This question is related to python performance

The answer is


Below code will find the max and the second max numbers without the use of max function. I assume that the input will be numeric and the numbers are separated by single space.

myList = input().split()
myList = list(map(eval,myList))


m1 = myList[0]
m2 = myList[0]

for x in myList:
    if x > m1:
        m2 = m1
        m1 = x
    elif x > m2:
        m2 = x

print ('Max Number: ',m1)
print ('2nd Max Number: ',m2)

You could always use sorted

>>> sorted(numbers)[-2]
74

Objective: To find the second largest number from input.

Input : 5 2 3 6 6 5

Output: 5

*n = int(raw_input())
arr = map(int, raw_input().split())
print sorted(list(set(arr)))[-2]*

>>> l = [19, 1, 2, 3, 4, 20, 20]
>>> sorted(set(l))[-2]
19

use defalut sort() method to get second largest number in the list. sort is in built method you do not need to import module for this.

lis = [11,52,63,85,14]
lis.sort()
print(lis[len(lis)-2])

If you do not mind using numpy (import numpy as np):

np.partition(numbers, -2)[-2]

gives you the 2nd largest element of the list with a guaranteed worst-case O(n) running time.

The partition(a, kth) methods returns an array where the kth element is the same it would be in a sorted array, all elements before are smaller, and all behind are larger.


You can find the 2nd largest by any of the following ways:

Option 1:

numbers = set(numbers)
numbers.remove(max(numbers))
max(numbers)

Option 2:

sorted(set(numbers))[-2]

Most of previous answers are correct but here is another way !

Our strategy is to create a loop with two variables first_highest and second_highest. We loop through the numbers and if our current_value is greater than the first_highest then we set second_highest to be the same as first_highest and then the second_highest to be the current number. If our current number is greater than second_highest then we set second_highest to the same as current numberenter image description here

#!/usr/bin/env python3
import sys
def find_second_highest(numbers):

    min_integer = -sys.maxsize -1
    first_highest= second_highest = min_integer
    for current_number in numbers:
        if current_number == first_highest and min_integer != second_highest:
            first_highest=current_number
        elif current_number > first_highest:
            second_highest = first_highest
            first_highest = current_number
        elif current_number > second_highest:
            second_highest = current_number
    return second_highest

print(find_second_highest([80,90,100]))
print(find_second_highest([80,80]))
print(find_second_highest([2,3,6,6,5]))

The quickselect algorithm, O(n) cousin to quicksort, will do what you want. Quickselect has average performance O(n). Worst case performance is O(n^2) just like quicksort but that's rare, and modifications to quickselect reduce the worst case performance to O(n).

The idea of quickselect is to use the same pivot, lower, higher idea of quicksort, but to then ignore the lower part and to further order just the higher part.


Max out the value by comparing each one to the max_item. In the first if, every time the value of max_item changes it gives its previous value to second_max. To tightly couple the two second if ensures the boundary

def secondmax(self, list):
    max_item = list[0]
    second_max = list[1]
    for item in list:
        if item > max_item:
            second_max =  max_item
            max_item = item
        if max_item < second_max:
            max_item = second_max
    return second_max

O(n): Time Complexity of a loop is considered as O(n) if the loop variables is incremented / decremented by a constant amount. For example following functions have O(n) time complexity.

 // Here c is a positive integer constant   
   for (int i = 1; i <= n; i += c) {  
        // some O(1) expressions
   }

To find the second largest number i used the below method to find the largest number first and then search the list if thats in there or not

x = [1,2,3]
A = list(map(int, x))
y = max(A)
k1 = list()
for values in range(len(A)):
if y !=A[values]:
    k.append(A[values])

z = max(k1)
print z

Just to make the accepted answer more general, the following is the extension to get the kth largest value:

def kth_largest(numbers, k):
    largest_ladder = [float('-inf')] * k
    count = 0
    for x in numbers:
        count += 1
        ladder_pos = 1
        for v in largest_ladder:
            if x > v:
                ladder_pos += 1
            else:
                break
        if ladder_pos > 1:
            largest_ladder = largest_ladder[1:ladder_pos] + [x] + largest_ladder[ladder_pos:]
    return largest_ladder[0] if count >= k else None

You can also try this:

>>> list=[20, 20, 19, 4, 3, 2, 1,100,200,100]
>>> sorted(set(list), key=int, reverse=True)[1]
100

def secondlarget(passinput):
    passinputMax = max(passinput)  #find the maximum element from the array
    newpassinput = [i for i in passinput if i != passinputMax]  #Find the second largest element in the array
    #print (newpassinput)
    if len(newpassinput) > 0:
        return max(newpassinput) #return the second largest
    return 0
if __name__ == '__main__':
    n = int(input().strip())  # lets say 5
    passinput = list(map(int, input().rstrip().split())) # 1 2 2 3 3
    result = secondlarget(passinput) #2
    print (result) #2

Best solution that my friend Dhanush Kumar came up with:

    def second_max(loop):
        glo_max = loop[0]
        sec_max = float("-inf")
        for i in loop:
            if i > glo_max:
                sec_max = glo_max
                glo_max=i
            elif sec_max < i < glo_max:
                sec_max = i
        return sec_max
    
    #print(second_max([-1,-3,-4,-5,-7]))
    
    assert second_max([-1,-3,-4,-5,-7])==-3
    assert second_max([5,3,5,1,2]) == 3
    assert second_max([1,2,3,4,5,7]) ==5
    assert second_max([-3,1,2,5,-2,3,4]) == 4
    assert second_max([-3,-2,5,-1,0]) == 0
    assert second_max([0,0,0,1,0]) == 0

You could use the heapq module:

>>> el = [20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7]
>>> import heapq
>>> heapq.nlargest(2, el)
[90.8, 74]

And go from there...


if __name__ == '__main__':
    n = int(input())
    arr = list(map(float, input().split()))
    high = max(arr)
    secondhigh = min(arr)
    for x in arr:
        if x < high and x > secondhigh:
            secondhigh = x
    print(secondhigh)

The above code is when we are setting the elements value in the list as per user requirements. And below code is as per the question asked

#list
numbers = [20, 67, 3 ,2.6, 7, 74, 2.8, 90.8, 52.8, 4, 3, 2, 5, 7]
#find the highest element in the list
high = max(numbers)
#find the lowest element in the list
secondhigh = min(numbers)
for x in numbers:
    '''
    find the second highest element in the list,
    it works even when there are duplicates highest element in the list.
    It runs through the entire list finding the next lowest element
    which is less then highest element but greater than lowest element in
    the list set initially. And assign that value to secondhigh variable, so 
    now this variable will have next lowest element in the list. And by end 
    of loop it will have the second highest element in the list  
    '''
    if (x<high and x>secondhigh):
        secondhigh=x
print(secondhigh)

This can be done in [N + log(N) - 2] time, which is slightly better than the loose upper bound of 2N (which can be thought of O(N) too).

The trick is to use binary recursive calls and "tennis tournament" algorithm. The winner (the largest number) will emerge after all the 'matches' (takes N-1 time), but if we record the 'players' of all the matches, and among them, group all the players that the winner has beaten, the second largest number will be the largest number in this group, i.e. the 'losers' group.

The size of this 'losers' group is log(N), and again, we can revoke the binary recursive calls to find the largest among the losers, which will take [log(N) - 1] time. Actually, we can just linearly scan the losers group to get the answer too, the time budget is the same.

Below is a sample python code:

def largest(L):
    global paris
    if len(L) == 1:
        return L[0]
    else:
        left = largest(L[:len(L)//2])
        right = largest(L[len(L)//2:])
        pairs.append((left, right))
        return max(left, right)

def second_largest(L):
    global pairs
    biggest = largest(L)
    second_L = [min(item) for item in pairs if biggest in item]

    return biggest, largest(second_L)  



if __name__ == "__main__":
    pairs = []
    # test array
    L = [2,-2,10,5,4,3,1,2,90,-98,53,45,23,56,432]    

    if len(L) == 0:
        first, second = None, None
    elif len(L) == 1:
        first, second = L[0], None
    else:
        first, second = second_largest(L)

    print('The largest number is: ' + str(first))
    print('The 2nd largest number is: ' + str(second))

Try the solution below, it's O(n) and it will store and return the second greatest number in the second variable. UPDATE: I've adjusted the code to work with Python 3, because now arithmetic comparisons against None are invalid.

Notice that if all elements in numbers are equal, or if numbers is empty or if it contains a single element, the variable second will end up with a value of None - this is correct, as in those cases there isn't a "second greatest" element.

Beware: this finds the "second maximum" value, if there's more than one value that is "first maximum", they will all be treated as the same maximum - in my definition, in a list such as this: [10, 7, 10] the correct answer is 7.

def second_largest(numbers):
    minimum = float('-inf')
    first, second = minimum, minimum
    for n in numbers:
        if n > first:
            first, second = n, first
        elif first > n > second:
            second = n
    return second if second != minimum else None

Here are some 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])
=> 1
second_largest([10, 7, 10])
=> 7
second_largest( [1, 3, 10, 16])
=> 10
second_largest([1, 1, 1, 1, 1, 1])
=> None
second_largest([1])
=> None
second_largest([])
=> None

Why to complicate the scenario? Its very simple and straight forward

  1. Convert list to set - removes duplicates
  2. Convert set to list again - which gives list in ascending order

Here is a code

mlist = [2, 3, 6, 6, 5]
mlist = list(set(mlist))
print mlist[-2]

    def SecondLargest(x):
        largest = max(x[0],x[1])
        largest2 = min(x[0],x[1])
        for item in x:
            if item > largest:
               largest2 = largest
               largest = item
            elif largest2 < item and item < largest:
               largest2 = item
        return largest2
    SecondLargest([20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7])

list_nums = [1, 2, 6, 6, 5]
minimum = float('-inf')
max, min = minimum, minimum
for num in list_nums:
    if num > max:
        max, min = num, max
    elif max > num > min:
        min = num
print(min if min != minimum else None)

Output

5

A simple way :

n=int(input())
arr = set(map(int, input().split()))
arr.remove(max(arr))
print (max(arr))

there are some good answers here for type([]), in case someone needed the same thing on a type({}) here it is,

def secondLargest(D):
    def second_largest(L):  
        if(len(L)<2):
            raise Exception("Second_Of_One")
        KFL=None #KeyForLargest
        KFS=None #KeyForSecondLargest
        n = 0
        for k in L:
            if(KFL == None or k>=L[KFL]):
                KFS = KFL
                KFL = n
            elif(KFS == None or k>=L[KFS]):
                KFS = n
            n+=1
        return (KFS)
    KFL=None #KeyForLargest
    KFS=None #KeyForSecondLargest
    if(len(D)<2):
        raise Exception("Second_Of_One")
    if(type(D)!=type({})):
        if(type(D)==type([])):
            return(second_largest(D))
        else:
            raise Exception("TypeError")
    else:
        for k in D:
            if(KFL == None or D[k]>=D[KFL]):
                KFS = KFL               
                KFL = k
            elif(KFS == None or D[k] >= D[KFS]):
                KFS = k
    return(KFS)

a = {'one':1 , 'two': 2 , 'thirty':30}
b = [30,1,2] 
print(a[secondLargest(a)])
print(b[secondLargest(b)])

Just for fun I tried to make it user friendly xD


n=input("Enter a list:")
n.sort()
l=len(n)
n.remove(n[l-1])
l=len(n)
print n[l-1]

you have to compare in between new values, that's the trick, think always in the previous (the 2nd largest) should be between the max and the previous max before, that's the one!!!!

def secondLargest(lista):
    max_number   = 0
    prev_number  = 0

    for i in range(0, len(lista)):

        if lista[i] > max_number:
            prev_number = max_number
            max_number  = lista[i]
        elif lista[i] > prev_number and lista[i] < max_number:
            prev_number = lista[i]

    return prev_number