Python get second smallest element nested lists recursion

Question

I want to return the 2nd smallest element from a nested list using recursion and no built in functions. i.e.

>>>ss([[[1,3],[2],3]])
2

I know how to get the maximum and minimum of such lists but I'm having trouble keeping track of the second smallest value.

What I wrote so far, which does return the correct smallest value but doesn't work for second smallest.

def ss(L):
smallest = L[0]
while type(smallest) == type([]):
    smallest = smallest[0]



second_smallest = smallest

for element in L:
    if type(element) == type([]):
        current = ss(element)
        if current > smallest and current < second_smallest:
            second_smallest = current            
        if current < smallest and current < second_smallest:
            second_smallest = smallest
            smallest = current      
    else:
        if smallest < element and element < second_smallest:
            second_smallest = element            
        if smallest > element and second_smallest > element:
            second_smallest =  smallest
            smallest = element


return second_smallest

Is there a way to make this work or should I look for a different approach?

score 0 · Answer 1 · answered Jun 28 '15 at 22:45

Well, once you solved it for a flat list, you can just write a function to flatten a list:

def secondSmallest(l):
    def iterflat(l):
        for i in l:
            if isinstance(i,(list,tuple)):
                yield from iterflat(i)
            else:
                yield i
    def min2(l,m1=float('inf'),m2=float('inf')):
        if l==[]: return (m1,m2)
        if l[0] > m2: return min2(l[1:],m1,m2)
        if l[0] > m1: return min2(l[1:],m1,l[0])
        if l[0] < m1: return min2(l[1:],l[0],m1)
    return min2(list(iterflat(l)))[1]

Test:

>>> secondSmallest([1,6,3,4,9,4,2,5,3,6,2])
2
>>> secondSmallest([1,6,3,4,9,[4,[9,8,-2,-3]],2,5,3,6,2])
-2

score 0 · Answer 2 · edited May 23 '17 at 12:06

0

Here is a quick solution that involves flattening the nested lists (or tuples), then finding the second lowest value. Note that this method will skip multiple instances of the lowest value. Inputting [1,1,1,2,3] will return 2. The list flattening method was taken from here.

def flatten(container):
    for i in container:
        if isinstance(i, list) or isinstance(i, tuple):
            for j in flatten(i):
                yield j
        else:
            yield i

def ss(container):
    tmp = list(set(flatten(container)))
    tmp.sort
    return tmp[1]

ss([1, 2, [3, 4, [5],[1]], [6, [[[7, 3]]]]])
>> 2

edited May 23 '17 at 12:06

Community

1
1

answered Jun 28 '15 at 22:48

James

32,991
4
47
70

`if isinstance(i, list) or isinstance(i, tuple)` --> `if isinstance(i, (list, tuple):` – fferri Jun 28 '15 at 22:55
`for j in flatten(i): yield j` --> `yield from flatten(j)` (Python 3.4) – fferri Jun 28 '15 at 22:56

Python get second smallest element nested lists recursion

2 Answers2