Find duplicate in list using built-in functions only

Question

I am a TOTAL Noob so please be gentle!

I have written this code:

def sorted_has_duplicate(numbers):
     numbers.sort()
     duplicate = False

     for num in range(len(numbers)-1):
         if numbers[num] == numbers[num + 1]:
             duplicate = True
             break
     return duplicate

The code runs fine and it does what it is supposed to do which is find the first duplicate value in a list if any and return True or False.

My question is how can I have the same function perform the same task if the list is not sorted (sorting is not allowed) and i can only use built in python functions?

For each item in the list, check if that item occurs elsewhere in the remainder of the list. If so, it's a duplicate. — John Gordon, Nov 14 '18 at 18:38
The duplicate I identified *also* ignores/removes 0 and None values; you don't need that functionality. The remaining solution is equivalent to the one answer you got. — Prune, Nov 14 '18 at 18:48

user2390182 · Accepted Answer · 2018-11-14T18:51:41.187

Collect nums in a set as you iterate:

def has_duplicate(numbers):
     seen = set()
     for num in numbers:
         if num in seen:
             return True
         seen.add(num)
     return False

You can also shorten this down to:

def has_duplicate(numbers):
     return len(numbers) != len(set(numbers))

This simply checks whether the list has as many elements as its set which by definition has no duplicates.

Note that both these set-based solutions run in linear time because of a set's O(1) contains-check. The naive brute force approach of searching for each element in the list remainder

def has_duplicate(numbers):
     for i, num in enumerate(numbers):
         if num in numbers[i+1:]:
             return True
     return False

is quadratic because of a list's O(N) contains-check.

Find duplicate in list using built-in functions only

1 Answers1