Python - Find second smallest number

As per the Python in-built function sorted

sorted(my_list)[0]

gives back the smallest number, and sorted(my_list)[1] does accordingly for the second smallest, and so on and so forth.


The function can indeed be modified to find the second smallest:

def second_smallest(numbers):
    m1 = m2 = float('inf')
    for x in numbers:
        if x <= m1:
            m1, m2 = x, m1
        elif x < m2:
            m2 = x
    return m2

The old version relied on a Python 2 implementation detail that None is always sorted before anything else (so it tests as 'smaller'); I replaced that with using float('inf') as the sentinel, as infinity always tests as larger than any other number. Ideally the original function should have used float('-inf') instead of None there, to not be tied to an implementation detail other Python implementations may not share.

Demo:

>>> def second_smallest(numbers):
...     m1 = m2 = float('inf')
...     for x in numbers:
...         if x <= m1:
...             m1, m2 = x, m1
...         elif x < m2:
...             m2 = x
...     return m2
... 
>>> print(second_smallest([1, 2, 3, 4]))
2

Outside of the function you found, it's almost just as efficient to use the heapq.nsmallest() function to return the two smallest values from an iterable, and from those two pick the second (or last) value. I've included a variant of the unique_everseen() recipe to filter out duplicate numbers:

from heapq import nsmallest
from itertools import filterfalse

def second_smallest(numbers):
    s = set()
    sa = s.add
    un = (sa(n) or n for n in filterfalse(s.__contains__, numbers))
    return nsmallest(2, un)[-1]

Like the above implementation, this is a O(N) solution; keeping the heap variant each step takes logK time, but K is a constant here (2)!

Whatever you do, do not use sorting; that takes O(NlogN) time.


Or just use heapq:

import heapq
def second_smallest(numbers):
    return heapq.nsmallest(2, numbers)[-1]

second_smallest([1, 2, 3, 4])
# Output: 2

a = [6,5,4,4,2,1,10,1,2,48]
s = set(a) # used to convert any of the list/tuple to the distinct element and sorted sequence of elements
# Note: above statement will convert list into sets 
print sorted(s)[1] 

Tags:

Python