Get the second largest number in a list in linear time

Question

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?

I think your second method (`O(N)`) is the best, because for large lists using a one-liner just because it is shorter is not a good idea. — Ashwini Chaudhary, Apr 25 '13 at 22:29
Is running through the list twice really a problem? It's still O(N), and when you're dealing with cases where the algorithmic complexity is already good enough (or N is small), guesses about performance are almost useless. You need to write it multiple ways and `timeit` each one (and do so on all platforms/implementations you care about). And, unless this is a bottleneck, that isn't worth the effort. — abarnert, Apr 25 '13 at 22:30
@abarnert, running twice through the list isn't a problem, but I'm trying to understand idiosyncracies of python before letting my students loose on it. I can see lots of cases where a student would take a list, run a transformation, another, another, and where the simple solution is the bad one. — boisvert, Apr 25 '13 at 22:39
Now `m2` will just be the largest if the first element is the largest. It also (I believe) fails to replace `m2` when `m2 — Volatility, Apr 25 '13 at 22:44
@boisvert: But the answer that's right for this toy example may not be—probably won't be—the answer that's right for a similar real-life case. For example, if you need to repeatedly get the top 2 as you continue to add to the list, you probably want to keep track of the top 2 as you go along and check each time you add, or keep the list continuously sorted (e.g., by using a tree-based collection like `blist.sortedlist` instead of a list). — abarnert, Apr 25 '13 at 22:49
@abarnert, so "keep track of the top 2", is the O(N) solution - except the loop waits for input - and "keep continuously sorted" is a different requirement. Though to keep sorting, I can imagine somebody will apply "sorted" to the list with every new input: again, the easy solution is the poor one. — boisvert, Apr 25 '13 at 23:04
@boisvert notice that the simplistic approach `numbers.remove(max(numbers))` can be troublesome for edge cases: if all the elements in the list are equal, if there's a single element in the list or if the list is empty. For those cases a hand-crafted (but longer) solution might yield better results, depending on the expected answer and the initial assumptions of the problem (for example: are there duplicates in the list?) see my answer for a series of tests dealing with those cases, and my take on them — Óscar López, Apr 25 '13 at 23:42
@boisvert: No, "keep track of the top 2 as you go along" is O(1) for each "get the top 2" call, and also O(1) for each "add a new value". Compare to "keep the list in a sorted tree", O(log N) and O(log N), "re-scan an unsorted list each get", O(N) and O(1), "re-sort/heap the list each get", O(N log N) and O(1), etc. — abarnert, Apr 26 '13 at 00:46
@boisvert: That being said, if you're adding a new value 1 billion times as often as you're getting the top 2 values, the fact that you've got a larger multiplier on all billion of those O(1) inserts may waste a lot more time than you save with the single O(1) vs. O(N) lookup. — abarnert, Apr 26 '13 at 00:47

score 79 · Answer 1 · edited Jun 08 '17 at 11:42

79

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...

edited Jun 08 '17 at 11:42

Natan Streppel

5,759
6
35
43

answered Apr 25 '13 at 22:23

Jon Clements

138,671
33
247
280

22

It is equivalent to : `sorted(iterable,reverse=True)[:n]`, still `NlogN` – Ashwini Chaudhary Apr 25 '13 at 22:25
3

@AshwiniChaudhary functionally equivalent to that, yes; however because of the implementation it performs fewer comparisons so is more efficient than sorting and slicing – Jon Clements Apr 25 '13 at 22:28
4

@JonClements: But O(NlogN) is still nowhere near as good as O(N) for large N, and the OP already has an O(N) solution, which is what (I think) Ashwini is pointing out. – abarnert Apr 25 '13 at 22:31
4

From a very cursory test, with 64-bit CPython 3.3.0 on my Mac, the crossover is somewhere near N=1000000. Above that, the OP's original code is significantly faster; below it, the reverse. – abarnert Apr 25 '13 at 22:35
… and `sorted` does seem to be slower than `heapq` pretty much across the board, and they continue to diverge the larger N gets, so your point is valid as well. – abarnert Apr 25 '13 at 22:39
@AshwiniChaudhary Equivalent but much faster. It's not NlogN – Itay Jul 24 '17 at 08:05
1

@AshwiniChaudhary I think this is equivalent to `h = heapq.heapify(list); heapq.heappop(h), second_largest = heapq.heappop(h)`. This is in O(n + log(n) + log(n)) = O(n). – Martin Thoma Mar 19 '20 at 07:32
O(NlogN) is pretty much O(N), people don't realize how slowly logN grows, for N = 10 ^ 100, which is pretty much the highest you could assume, it would still be O(100N) which is O(N) – Abhishek Choudhary Dec 24 '21 at 13:32
2

@AbhishekChoudhary your comment is *very* wrong, and not only for pedantic technical reasons. – Zakaria Jan 06 '22 at 15:53
2

@Zakaria I obviously didn't imply that it's same, but saying Nlog(N) is much worse than N is very incorrect, even O(N) can be any multiple of N, and given the extremely slow rate of growth of logN, an NlogN solution would be preferred. Also, It was in reply to this comment above `But O(NlogN) is still nowhere near as good as O(N) for large N, and the OP already has an O(N) solution, which is what (I think) Ashwini is pointing out.` – Abhishek Choudhary Jan 06 '22 at 16:26
@Ashwini Chaudhary This is O(N), not NlogN. (And already was back when you posted that first comment). – Kelly Bundy Feb 01 '22 at 14:18

Thijs van Dien · Accepted Answer · 2019-08-20T14:57:03.670

36

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.

edited Aug 20 '19 at 14:57

answered Apr 25 '13 at 23:15

Thijs van Dien

6,516
1
29
48

1

That is the functionality identical to finding max, removing, and finding max of the rest. – boisvert Apr 25 '13 at 23:23
@boisvert and what happens if there are several values with the same `max`? do yo remove all of them or just one? – Óscar López Apr 25 '13 at 23:27
1

@OscarLopez `list.remove()` removes only the first matching element found. – Thijs van Dien Apr 25 '13 at 23:28
@OscarLopez Well, he posted working code, so I consider the removing implemented. – Thijs van Dien Apr 25 '13 at 23:34
@ThijsvanDien, that is the functionality I was looking for. Accepting. – boisvert Apr 26 '13 at 06:54
2

You should not rely on Python 2 implementation details; the sort order of `None` is an arbitrary choice. Use `float('inf')` instead. – Martijn Pieters Nov 06 '14 at 12:48
1

@MartijnPieters The function should not return negative infinity (a number that could've been present) when the answer is actually undefined, though. Updated the answer to take that into account. – Thijs van Dien Nov 10 '14 at 21:00
@ThijsvanDien: Nice, I like the iterative approach here. – Martijn Pieters Nov 10 '14 at 21:38
Good job! By the way, this answer can be extented to get the kth largest value. See my answer for an example. – Bily Jan 09 '19 at 05:44
@Bily It can be, but you need to be careful to not end up fooling yourself. When the constant becomes large enough, you can no longer consider it insignificant. You'd then have `O(kn)`. As `k` approaches `n`, what you really have is `O(n^2)`. – Thijs van Dien Jan 09 '19 at 18:47
1

This is not working with `[2,3,6,6,5]` the output is `6` instead of `5` – Shivam Bharadwaj May 12 '20 at 12:38
1

@ShivamBharadwaj Read the whole answer and you'll see it works as intended. – Thijs van Dien May 14 '20 at 00:12

score 24 · Answer 3 · answered Apr 25 '13 at 22:21

24

You could always use sorted

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

answered Apr 25 '13 at 22:21

Volatility

31,232
10
80
89

4

I don't understand why people are accepting this, not only is it not O(N), it's not even the same, it just sorts and picks 2nd from the end, if there are more than 1 maximum, it will give an incorrect answer, you would need another loop after sorting to pick actual 2nd largest, which is bad cuz O(N) solution already exists. – Abhishek Choudhary Dec 24 '21 at 13:34

Óscar López · Answer 4 · 2019-12-27T14:26:02.770

21

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

edited Dec 27 '19 at 14:26

answered Apr 25 '13 at 22:51

Óscar López

232,561
37
312
386

1

It goes wrong if the maximum value occurs more than once. It should be `if n >= first`. Or do we consider duplicates as one? – Thijs van Dien Apr 25 '13 at 23:06
@ThijsvanDien I can't reproduce the error, can you provide a list to use as counterexample? and yes, I consider duplicates as one – Óscar López Apr 25 '13 at 23:08
`[20,67,3,2.6,7,74,2.8,90.8,52.8,4,3,2,5,7,90.8]`, desired result: 90.8, actual result: 74. – Thijs van Dien Apr 25 '13 at 23:09
@ThijsvanDien mmm no, 74 _is_ the desired result. 90.8 and 90.8 are both the maximum, the second maximum is 74 – Óscar López Apr 25 '13 at 23:10
Well, that depends on the definition. The first algorithm provided by the OP defines that the second largest may be the same as the largest. – Thijs van Dien Apr 25 '13 at 23:11
OK, I'll clarify that in my definition, all maximums with the same value are considered to be the same – Óscar López Apr 25 '13 at 23:12
@ÓscarLópez, your tests and answer got us there, so thanks. And yes, I should pay attention to specs in my questions. – boisvert Apr 26 '13 at 06:58
1

the second condition: `elif first > n > second: second = n` will never be met, there for should be removed – Roy learns to code Oct 27 '17 at 00:08
This gives error `TypeError: '>' not supported between instances of 'int' and 'NoneType'` – Nikhil Talreja Dec 23 '19 at 11:34
@NikhilTalreja for what input data? Perhaps there are None values in your array? – Óscar López Dec 23 '19 at 13:37
@Roylearnstocode that's not correct, the case is mandatory, if you remove it you'd be missing the case when a new "second" is found, greater than the current one but smaller than the first. Try running my test cases against your proposed change and some of the tests will now fail. – Óscar López Dec 23 '19 at 18:11
@ÓscarLópez my list is [1,3,10,16] – Nikhil Talreja Dec 27 '19 at 08:50
1

@NikhilTalreja thanks for reporting the bug! I've updated my code with the fix, adding your test case. The error started happening in Python 3, because now we can't do arithmetic comparisons against `None`. – Óscar López Dec 27 '19 at 14:17

score 5 · Answer 5 · answered Jul 12 '18 at 16:12

5

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]

answered Jul 12 '18 at 16:12

Sahil Chhabra

10,621
4
63
62

score 4 · Answer 6 · answered Jun 13 '15 at 18:36

4

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.

answered Jun 13 '15 at 18:36

Edward Doolittle

4,002
2
14
27

1

@edward_doolittle, That's a very interesting idea. Part of my initial question was that the efficient solution wasn't 'neat'. An more general algorithm means that the not-so-neat elements of implementation can be factored away, at least in this case. – boisvert Nov 15 '15 at 21:49
1

This is used in numpy.partition (actually, it's the introselect algorithms, which upgrades quickselect). See f.ex. http://stackoverflow.com/a/43171040/1587329 – serv-inc Apr 02 '17 at 17:37

score 4 · Answer 7 · answered Nov 07 '16 at 07:36

4

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

Convert list to set - removes duplicates
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]

answered Nov 07 '16 at 07:36

Abhishek Kulkarni

3,693
8
35
42

3

The problem is the time taken for these operations (and, incidentally, duplicates wasn't my first problem). The sorting operation is O(n*log(n)), but finding the largest (without sorting) is linear ( O(n) ) since it takes one loop. A naive solution takes two loops: O(2n). A not-so-naive one should take one loop, seeking largest and second largest in a single pass. My real problem - not really answered here - is this: the single pass solutions are complex to read and write, in other words, python is not so good at making complex processing simple to express, as we like to say it is. – boisvert Nov 09 '16 at 10:54
2

*"Convert set to list again - which gives list in ascending order"* - citation needed... `list({400, 2, 100})` gives `[400, 2, 100]` so I'm not sure how this answers the question... (Maybe that works for specific small integers, but not always) – Tomerikoo Mar 13 '22 at 12:10
@Tomerikoo it's just the wrong assumption. List construction doesn't sort elements – Michael Berdyshev Feb 04 '23 at 10:23

Ganesh Patil · Answer 8 · 2023-02-22T11:38:24.680

4

This is one of the Simple Way

def find_second_largest(arr):
    first, second = float('-inf'), float('-inf')

    for number in arr:
        if number > first:
            second = first
            first = number
        elif second < number < first:
            second = number

    return second

edited Feb 22 '23 at 11:38

answered Oct 19 '21 at 11:58

Ganesh Patil

105
1
7

2

Unfortunately this solution doesnt't work if all numbers are below zero – Michael Berdyshev Feb 04 '23 at 18:34
1

I have edited the script.. hope it works as expected now @MichaelBerdyshev – Ganesh Patil Feb 22 '23 at 11:39

score 2 · Answer 9 · answered Apr 02 '17 at 17:03

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.

kpie · Answer 10 · 2015-01-13T16:43:12.320

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

Bharatwaja · Answer 11 · 2016-10-24T05:56:07.653

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

Please add a description to explain your answer. – Murray Foxcroft Aug 02 '16 at 06:44 — Murray Foxcroft, Aug 02 '16 at 06:44

score 1 · Answer 12 · answered Apr 30 '18 at 22:33

    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])

score 1 · Answer 13 · answered Jan 09 '19 at 05:39

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

score 1 · Answer 14 · answered May 12 '20 at 12:55

1

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

answered May 12 '20 at 12:55

Shivam Bharadwaj

1,864
21
23

score 1 · Answer 15 · answered Aug 17 '22 at 13:11

Using reduce from functools should be a linear-time functional-style alternative:

from functools import reduce

def update_largest_two(largest_two, x):
    m1, m2 = largest_two
    return (m1, m2) if m2 >= x else (m1, x) if m1 >= x else (x, m1)


def second_largest(numbers):
    if len(numbers) < 2:
        return None
    largest_two = sorted(numbers[:2], reverse=True)
    rest = numbers[2:]
    m1, m2 = reduce(update_largest_two, rest, largest_two)
    return m2

... or in a very concise style:

from functools import reduce

def second_largest(n):
    update_largest_two = lambda a, x: a if a[1] >= x else (a[0], x) if a[0] >= x else (x, a[0])

    return None if len(n) < 2 else (reduce(update_largest_two, n[2:], sorted(n[:2], reverse=True)))[1]

@Michael Berdyshev Please think again :-) `sorted` is O(N*log(N)), but in the length of its input, not in the length of the list `numbers`. You can solve the halting problem in constant time if you limit its input to constant length. — Bernhard Stadler, Feb 25 '23 at 09:43

Brent D. · Answer 16 · 2015-07-21T22:59:13.763

0

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

edited Jul 21 '15 at 22:59

answered Jul 21 '15 at 22:52

Brent D.

543
2
7

As with the other solution you commented on, this is not likely to be linear – Foon Jul 22 '15 at 02:28
1

Like several of the other solutions, calling sorted gives the result, but it doesn't do it efficiently. – boisvert Nov 15 '15 at 21:43

ccy · Answer 17 · 2016-09-29T05:54:37.423

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))

I don't see how this algorithm is supposed to have a logarithmic component. `largest` runs through the whole list `L` and builds a list `pairs` of length `len(L) / 2` (one element per inner node of the binary recursion tree). Then `second_largest` runs through `pairs`, which takes at least 1.5 * N. — Bernhard Stadler, Mar 03 '23 at 07:44

score 0 · Answer 18 · edited Oct 24 '17 at 08:59

0

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]*

edited Oct 24 '17 at 08:59

Abdul Rasheed

6,486
4
32
48

answered Oct 24 '17 at 08:14

Rakesh TS

47
4

2

I see no difference from [this](https://stackoverflow.com/a/31550994/4249707) answer – El Ruso Oct 24 '17 at 08:30
What value does this answer add relative to all the other answers posted here months and years ago? – Jean-François Corbett Oct 24 '17 at 08:46

score 0 · Answer 19 · answered Mar 06 '20 at 16:47

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

score 0 · Answer 20 · edited Mar 04 '23 at 04:34

Best solution that my friend Dhanush Kumar came up with:

    def second_max(numbers):
        glo_max = numbers[0]
        sec_max = float("-inf")
        for i in numbers:
            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

score -1 · Answer 21 · answered Oct 24 '16 at 05:54

-1

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

answered Oct 24 '16 at 05:54

Vikram Singh Chandel

1,290
2
17
36

1

How do you get `sorted()` to execute in *O(n)* time? It's usually *O(n log n)* – Toby Speight Apr 23 '18 at 12:41

rashedcs · Answer 22 · 2017-12-18T15:56:28.717

-1

A simple way :

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

edited Dec 18 '17 at 15:56

answered Dec 18 '17 at 15:41

rashedcs

3,588
2
39
40

saigopi.me · Answer 23 · 2018-04-23T12:41:25.717

-1

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])

edited Apr 23 '18 at 12:41

answered Apr 23 '18 at 12:20

saigopi.me

14,011
2
83
54

Thank you for this code snippet, which might provide some limited short-term help. A proper explanation [would greatly improve](//meta.stackexchange.com/q/114762) its long-term value by showing *why* this is a good solution to the problem, and would make it more useful to future readers with other, similar questions. Please [edit] your answer to add some explanation, including the assumptions you've made. In particular, how do you get a `sort()` implementation that works in *O(n)*? – Toby Speight Apr 23 '18 at 12:38
What if the max number repeats? This will just return the max, not *second* max – Tomerikoo Mar 13 '22 at 12:15
This suggested solution modifies the input list and runs in O(n*log(n)) time, while the author of the question asks for a non-destructive and linear solution which runs through the list only once. – Bernhard Stadler Feb 25 '23 at 15:35

grepit · Answer 24 · 2020-05-13T20:23:20.793

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 number

#!/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]))

With your code, `find_second_highest([90, 90, 80]) == 90`, but `find_second_highest([90, 80, 90]) == 80` and `find_second_highest([80, 90, 90]) == 80`. The first 'if' case is the problem. — Bernhard Stadler, Mar 03 '23 at 10:28

score -1 · Answer 25 · answered Aug 19 '19 at 06:58

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

Nisrin Dhoondia · Answer 26 · 2019-10-08T07:28:51.190

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)

Please add some explaining text to your answer, and explain how it relates to the examples of the question. You should probably also write code that treats the `numbers` variable defined in the question. — beruic, Oct 02 '19 at 12:11
better, but this is not much faster than the users code, because you use both `max` and `min`. A quick optimization is that instead of spending `O(n)` time on finding the minimum, you could use `secondhigh = float('-inf')` instead. As long as the list contains more than one element, `secondhigh` will be replaced. If the list is to short, you should take that into consideration as well. — beruic, Oct 08 '19 at 08:00

score -1 · Answer 27 · edited Dec 26 '19 at 01:51

-1

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

edited Dec 26 '19 at 01:51

Trenton McKinney

56,955
33
144
158

answered Dec 25 '19 at 12:31

Ankit

45
4

Does not work: `>>> for l in lsts: print(f"{l}: {secondmax(l)}; ") [0, 0]: 0; [0, 1]: 1; [1, 0]: 0; [0, 0, 0]: 0; [0, 0, 1]: 0; [0, 1, 0]: 1; [1, 0, 0]: 0; [1, 1, 0]: 1; [1, 0, 1]: 0; [0, 1, 1]: 1; ` – Bernhard Stadler Feb 25 '23 at 16:41

Salman · Answer 28 · 2021-02-07T01:24:58.680

-1

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)

edited Feb 07 '21 at 01:24

answered Feb 06 '21 at 17:22

Salman

1,236
5
30
59

Won't generalize – Ahmad Farhan Sep 30 '21 at 19:52
This will throw an exception for empty lists and print the largest number for single-element lists. – Bernhard Stadler Feb 25 '23 at 15:59

score -1 · Answer 29 · answered Apr 22 '21 at 11:27

-1

Here I tried to come up with an answer. 2nd(Second) maximum element in a list using single loop and without using any inbuilt function.

def secondLargest(lst):
    mx = 0
    num = 0
    sec = 0
    for i in lst:
        if i > mx:
            sec = mx
            mx = i
        else:
            if i > num and num >= sec:
                sec = i
            num = i
    return sec

answered Apr 22 '21 at 11:27

varun

27
7

This is almost identical to the algorithm stated in the question, except it assumes that all numbers in the are positive. Also, what is `num` supposed to be good for? It always remembers the previous element that is not larger than the maximum, except in the first two runs through the loop. – Bernhard Stadler Feb 25 '23 at 15:42

score -1 · Answer 30 · answered Nov 17 '21 at 08:09

We can use 2 loop to compare and find the second largest number from list rather than removing max number from list:

def second_largest(list1):
   second_max = list1[0]
   max_nu = max(list1)

   for i in range(len(list1) -1):
       for j in range(1,len(list1)):
          if list1[i] > list1[j] and list1[i] < max_nu :
              second_max = list1[i]
          elif list1[i] < list1[j] and list1[j] < max_nu:
              second_max = list1[j]
   return second_max

l = [2, 4, 5, 6, 8, 7, 21, 20]
print(second_largest(l))

This runs in O(n^2) time, i.e. it runs through the whole list n-1 times instead of the 2 times the author of the question wanted to improve upon. — Bernhard Stadler, Feb 25 '23 at 15:33

Get the second largest number in a list in linear time

30 Answers30

Linked

Related