How to find duplicates of list of arbitrary sized lists in < n^2 time in python?

Question

How do I find duplicates in the list of lists in < n^2 in python? I cannot use a dictionary to do it in linear time as if I did with all standard types. I can only think of the following solution:

arr = [[1,2], [1,2,4], [1,2], [5,6], [8], [8]]
unique_arr = []
dups = []

for item in arr:
    for item2 in unique_arr:
         if (item == item2).all():
            dups.append(item)
            continue
    unique_arr.append(item)

expected result for dups is [[1,2], [8]]

Thanks

You could convert your lists to something hashable since they just contain integers. Tuples are hashable. — user3483203, Jul 29 '19 at 19:58
@Tyger is it? in that question, all answers are mostly specific to the case where you have this format [value, counter]. I have a list of arbitrary sized lists... — YohanRoth, Jul 29 '19 at 20:06

Andrej Kesely · Accepted Answer · 2019-07-29T20:14:57.407

4

One possible solution with collections.Counter:

arr = [[1,2], [1,2,4], [1,2], [5,6], [8], [8]]

from collections import Counter

print([[*i] for i,c in Counter(map(tuple, arr)).items() if c > 1])

Prints:

[[1, 2], [8]]

OR:

Version with itertools.groupby and sorted:

from itertools import groupby
print([v for v, g in groupby(sorted(arr, key=len)) if any(i > 0 for i, _ in enumerate(g))])

Prints:

[[8], [1, 2]]

edited Jul 29 '19 at 20:14

answered Jul 29 '19 at 20:01

Andrej Kesely

168,389
15
48
91

and what complexity is that? – YohanRoth Jul 29 '19 at 20:08
1

`collections.Counter` is O(n) – user3483203 Jul 29 '19 at 20:08
1

@YohanRoth As @user3483203 staded, version with `Counter` is O(n). Version with groupby/sorted is O(nlogn) for sorted and O(n) for groupby – Andrej Kesely Jul 29 '19 at 20:11
Worth noting that neither of these options preserves order, if that matters to you – Cireo Jul 29 '19 at 22:48

score 0 · Answer 2 · answered Jul 29 '19 at 19:59

0

I don't see why you would need to iterate through the internal lists... You can simply iterate the outer list.

arr = [[1,2], [1,2,4], [1,2], [5,6], [8], [8]]
unique_arr = []
dups = []

for item in arr:
    if item not in unique_arr:
        unique_arr.append(item)
    else:
        unique_arr.append(item)

answered Jul 29 '19 at 19:59

jdub

1

I think "not in" functionality is implemented as a loop too. So it is the same stuff – YohanRoth Jul 29 '19 at 20:02
1

This still has the same complexity, just way faster because the list comparison is probably in C instead of python, and using an algorithm that is correct – Cireo Jul 29 '19 at 20:02
@Cireo oh I see, sure. But the actual time complexity is the same, while I am looking for smth < n^2 – YohanRoth Jul 29 '19 at 20:04

Er. Harsh Rathore · Answer 3 · 2019-07-29T20:55:56.447

0

Here is one more solution for you:

arr = [[1,2], [1,2,4], [1,2], [5,6], [8], [8]]

dic = {}
dups = []

for ele in arr:
    try:
        if dic[str(ele)] is 1:
            dups.append(ele)
    except:
        dic[str(ele)] = 1


print(dups)

output:

[[1, 2], [8]]

edited Jul 29 '19 at 20:55

answered Jul 29 '19 at 20:04

Er. Harsh Rathore

758
1
7
21

popping from front of the list is O(n) so this would be O(n^2)? – Manvir Jul 29 '19 at 20:13
its still O(n^2) since `if popped in arr:` is O(n) – Manvir Jul 29 '19 at 20:40
@Tyger Now What about the complexity? – Er. Harsh Rathore Jul 29 '19 at 20:57
@Tyger accessing or inserting the data to a dictionary has the complexity O(1). – Er. Harsh Rathore Jul 29 '19 at 20:58
I like your persistence you might wanna check this [out](https://stackoverflow.com/questions/1835756/using-try-vs-if-in-python) – Manvir Jul 29 '19 at 21:06
Okay I agree with you timing of accepted code is 24.07005401099923 and timing of my code is 26.193061662999753. – Er. Harsh Rathore Jul 29 '19 at 21:23

score 0 · Answer 4 · answered Jul 29 '19 at 20:06

While you can't use lists as dictionary keys, you can use tuples.

arr = [[1,2], [1,2,4], [1,2], [5,6], [8], [8]]
dups = []
found = set()
for item in arr:
    tup = tuple(item)
    if tup in found:
        dups.append(list(tup))
    found.add(tup)
print(dups)

How to find duplicates of list of arbitrary sized lists in < n^2 time in python?

4 Answers4