Second highest value of a python list

Question

I want to find the second highest value of a list without deleting any elements in it; I tried using the min and max command, but this only works with higher and lower. In case I want you to return number 5.

lista = [4, 5, 6]

Answer 1

I present below some alternatives to the solution with sorted (see reply of Paulo Marques).

Python has the function nlargest that returns the n larger elements of a list using a heap size n. In accordance with python documentation, for numbers of n small (like 2) this function is quite efficient.

import heapq
print(heapq.nlargest(2, lista)[-1])

From the theoretical point of view this solution has complexity O(n*log(2)) and memory consumption O(2). The solution with sorted has complexity O(n*log(n)) and memory consumption O(n)

Another alternative is to make a copy of the list, remove the maximum and then get the maximum from the resulting list (so the original list is not modified):

copia_lista = lista.clone()
copia_lista.remove(max(copia_lista))
print(max(copia_lista))

That solution is O(n) in space and time.

Finally you can also scroll through the list keeping the two largest numbers as per that question from Soen. Here is my variation of the answer accepted in Soen:

def second_largest(numbers):
    if len(numbers) < 2:
        return None
    m1 = m2 = float('-inf')
    for x in numbers:
        if x > m2:
            if x >= m1:
                m1, m2 = x, m1            
            else:
                m2 = x
    return m2

print(second_largest(lista))

That solution is O(n) in time and O(2) in space.

NOTE: The theoretically fastest algorithm will not necessarily be the fastest in practice. A performance of each algorithm can also be quite sensitive to the size and content of the original list.

Answer 2

A simple solution would be:

1. Sort the list in descending order
2. Take the second element

>>> lista = [1, 3, 2, 10, 7]

>>> print(sorted(lista, reverse=True)[1])
7

However, if you have repeated numbers in the list, the ideal is to take the set of the same:

>>> lista = [1, 3, 2, 10, 7, 10, 7, 3 ,2]

>>> print(sorted(lista, reverse=True)[1])  # Não funciona, pois a lista ordenada é [10, 10, 7, 7, 3, 3, 2, 2, 1]
10

>>> print(sorted(set(lista), reverse=True)[1])  # Agora sim, o set não aceita duplicados, sendo assim a lista é ordenada é [10, 7, 3, 2, 1]
7

I hope it helps