Using Python, Is there a more elegant way to find the second largest number in a list?

Question

I had this question come up in a job interview, and I was wondering if there were different ways to solve this. Preferably using Python 3.

Given a list of [20,40,20,60,80] find the second highest number.

The idea is to remove the duplicates. In one solution I've iterated over the list, and added any unique values to a list of uniques. Another way I did it was to convert the list to a set and back to a list, and then grab the second number.

So here's the question. Is there a better way to do this using Python 3?

Here's my code for solving in two different ways.

def second_item_method_1():

    my_list = [20,40,20,60,80]
    my_set  = set(my_list)
    my_list = list(my_set)
    my_list.sort()

    print(my_list[1])

def second_item_method_2():
    my_list = [20,40,20,60,80]
    unique_list = []

    for x in my_list:
        if x not in unique_list:
            unique_list.append(x)

    print(my_list[1])

second_item_method_1()
second_item_method_2()

Any other possible solutions?

I think you've covered the two obvious ways of doing this. For large lists, the `sort()` option would probably work best, assuming Python is using some divide-and-conquer algorithm under the hood. For smaller lists, your iteration method would probably work the best. — Tim Biegeleisen, Apr 26 '20 at 02:58
Answered here: https://stackoverflow.com/questions/16225677/get-the-second-largest-number-in-a-list-in-linear-time — ZaxR, Apr 26 '20 at 03:06
Your first method is unecessarily convoluted, just do `sorted(set(mylist))[1]` your second method is inefficient, `if x not in unique_list` makes the algorithm unecessarily quadratic time — juanpa.arrivillaga, Apr 26 '20 at 03:06
Does this answer your question? [Get the second largest number in a list in linear time](https://stackoverflow.com/questions/16225677/get-the-second-largest-number-in-a-list-in-linear-time) — ZaxR, Apr 26 '20 at 03:07
@juanpa.arrivillaga *cough* `reverse=true` or `[-1]` *cough* — Nick is tired, Apr 26 '20 at 03:09

Todd · Answer 1 · 2020-04-27T00:23:56.497

0

Simplest thing I could come up with constraining myself to a single pass through the numbers.

Finds the two highest values. Only returns duplicates if no other alternative value in the list.

>>> def two_highest(li):
...     a, b = li[:2]
...     for i in li[1:]:
...         if i > a:
...             a, b = i, a
...         elif i > b and i != a or a == b:
...             b = i
...     return (a, b)

edited Apr 27 '20 at 00:23

answered Apr 26 '20 at 06:19

Todd

4,669
1
22
30

score 0 · Answer 2 · answered Apr 26 '20 at 09:50

0

You can iterate over the list twice in first iteration you can find the maximum element and in second iteration find the maximum element which is smaller than the first element.

answered Apr 26 '20 at 09:50

Anirudha_singh

1
1

Single iteration is sufficient to find the second max item. – thatisvivek Apr 26 '20 at 18:39

score 0 · Answer 3 · answered Apr 26 '20 at 11:00

def third_item_method():
    list1 = [20, 40, 20, 60, 80]
    mx=max(list1[0],list1[1])
    secondmax=min(list1[0],list1[1]) 
    n =len(list1)
    for i in range(2,n):
       if list1[i]>mx:  
           secondmax=mx 
           mx=list1[i]  
       elif list1[i]>secondmax and mx != list1[i]:  
           secondmax=list1[i] 
       else: 
       if secondmax == mx: 
           secondmax = list1[i] 

     print("Second highest number is : ",str(secondmax)) 
third_item_method()

source: https://www.geeksforgeeks.org/python-program-to-find-second-largest-number-in-a-list/

Using Python, Is there a more elegant way to find the second largest number in a list?

3 Answers3