Extracting the deepest list or lists in a nested list

Question

I am new to python and struggling with nested lists. In particular, I have been given a nested list from which I need to extract the deepest list (or lists, if there are more than one list at the deepest depth). I've coded the below, but it's only returning one of the two deepest lists (the other one would be [4421, 4422]). Could someone explain what I'm doing wrong? There's a related question from before but, similarly, the suggested solutions could only provide the first of two deepest lists. Thank you.

def deepest_list(l):
    deeps = []
    for item in l:
        if isinstance(item, list):
            return deepest_list(item)
        else:
            deeps.append(item)
        continue
    return deeps

deepest_list([1, [21, [[2211, 2212], 222]], [[311], 32, [331]], [41, 42, 43, [441, [4421, 4422]]]])

Answer 1

There are two issues you need to deal with:

1. When you do return deepest_list(item) it breaks the execution of the function, including the loop, so any remaining items are not considered.

2. The straight-forward recursive logic, on which the code is based, is not suitable for the problem. It is not enough to find the deepest list(s) in any given sublist, you also need to know its depth, in order to compare it with the deepest list(s) in another sublist. In other words, correct code would have to remember the depth as well as the identity of the deepest list(s).

Answer 2

Try this:

def deepest_lists(lst):
    lsts = [item for item in lst if isinstance(item, list)]
    if len(lsts) == 0:
        return lsts
    if all(isinstance(item, int) for lst in lsts for item in lst):
        return lsts
    return deepest_lists([item for lst in lsts for item in lst])

Example:

>>> lst = [1, [21, [[2211, 2212], 222]], [[311], 32, [331]], [41, 42, 43, [441, [4421, 4422]]]]
>>> deepest_lists(lst)
[[2211, 2212], [4421, 4422]]

Answer 3

I would divide the problem in three parts:

1. You can find the sequence of indices needed to get to each innermost list in the list (e.g., if you have l = [[1,2], [[23, [12]]], the indices to get to 1 would be (0,0), as you would access it as l[0][0], and the indices to get to 2 would be (1,)).
2. From these indices, you can select the ones with the highest length, as they represent the deepest list.
3. From the original list, you select the elements that are represented in the list of the deepest indices.

Something like the following:

# Get from original list, using a list of tuples representing the indices of the wanted elements

def LookupByTuple(data, tuples):
    ret = []
    for t in tuples:
        answer = data
        for i in t:
            answer = answer[i]
        ret.append(answer)
    return ret

def deepest_ids(data, id=(), indices = set()):
    # Find the indices to get to each innermost list
    for i,elem in enumerate(data):
        if isinstance(elem, list):
            deepest_ids(elem, id + (i,), indices)
        else:
            indices.add(id)
    ids = list(indices)
    indices = None

    # Select the deepest indices
    maxlen = max(map(len, ids))
    ret = [s for s in ids if len(s) == maxlen]
    
    return ret

Which then gives you

>> l = [1, [21, [[2211, 2212], 222]], [[311], 32, [331]], [41, 42, 43, [441, [4421, 4422]]]]
>> LookupByTuple(l, deepest_ids(l))
>> [[4421, 4422], [2211, 2212]]

This solution works also when the input list only has one level:

>> l = [1,2,3]
>> LookupByTuple(l, deepest_ids(l))
>> [[1,2,3]]