Return second smallest number in a nested list using recursion

Question

I have to return the second smallest number in a python list using recursion, and no loops. What I have done is created a helper function that returns a tuple of the (smallest, second smallest) values in the list, and then I just take the tuple[1] in my second_smallest func.

def s_smallest(L):

    if(len(L) == 2):
        if (L[0] >= L[1]):
            return (L[1],L[0])
        else:
            return (L[0],L[1])
    else:
        first_smallest,second_smallest = s_smallest(L[1:])

        if L[0] >= first_smallest and L[0] <= second_smallest:
            return (first_smallest, L[0])

        elif L[0] <= first_smallest:
            return (L[0], first_smallest)

        else:
            return (first_smallest, second_smallest)

This works, but now I need to handle nested lists, so s_smallest([1,2,[3,0]]) should return (0,1). I tried doing this:

if isinstance(L[0],list):
    first_smallest,second_smallest = s_smallest(L[0])
else:
    first_smallest,second_smallest = s_smallest(L[1:])

to get the first smallest and second smallest values if it is a list, but I get an error saying builtins.TypeError: unorderable types: int() >= list(). How can I fix this problem to deal with nested lists?

Answer 1

I might suggest separating the list unnesting and the min reducing into two separate, well-defined tasks

• deepReduce will reduce a list of lists using the specified reducing function
• deepMin performs a deepReduce using min

import math # used for math.inf

def min (x,y):
  return x if x < y else y

def deepReduce (f, y, xs):
  if not xs:
    return y
  elif isinstance(xs[0], list):
    return deepReduce(f, deepReduce(f, y, xs[0]), xs[1:])
  else:
    return deepReduce(f, f(y, xs[0]), xs[1:])

def deepMin (xs):
  return deepReduce (min, math.inf, xs)


data = [1,2,[7,[6,1,3,[0,4,3]],3,4],2,1]
print(deepMin(data))
# 0

Oh, but you said you want the second smallest number. Let's rework that code a little bit. Of course I knew that all along, but answering this question twice allows me to demonstrate the versatility of this specific implementation – Changes in bold

def min2 (xs, y):
  # x1 is the smallest, x2 is second smallest
  x1, x2 = xs
  if (y < x1) and (y < x2):
    return (y, x2)
  elif y < x2:
    return (x1, y)
  else:
    return (x1, x2)

def deepMin2 (xs):
  # notice we change to use tuple of math.inf now
  x1, x2 = deepReduce (min2, (math.inf, math.inf), xs)
  return x2

data = [1,2,[7,[6,1,3,[0,4,3]],3,4],2,1]
print(deepMin2(data))
# 1

I should point out that we didn't have to touch deepReduce at all, which is the point – we should be able to do any arbitrary deep operation on our nested list without having to statically code that behaviour into our function.

Now you can write whatever deep reducer you want and call it with deepReduce