In this article we will discuss different ways to check if a list contains any duplicate element or not.

Suppose we have a list of elements i.e.

Now we want to check if this list contains any duplicate element or not. There are several ways to do this, but here we will discuss 3 ways and will also analyze there performance.

Check for duplicates in a list using Set & by comparing sizes

To check if a list contains any duplicate element follow the following steps,

  1. Add the contents of list in a set.
    • As set contains only unique elements, so no duplicates will be added to the set.
  2. Compare the size of set and list.
    • If size of list & set is equal then it means no duplicates in list.
    • If size of list & set are different then it means yes, there are duplicates in list.

We have created a function that follows the above Algo i.e.

Now let’s use this function to check if our list contains any duplicate or not i.e.

Output

Complexity Analysis of this solution.

As we are creating a set from list, so complexity will be n(log(n)). Comparing size is a O(1) operation. So, complexity of this solution is n(log(n)).

Even in best scenario i.e. if list contains only duplicated element, still this solution’s complexity will be n(log(n)) because we are just adding all the elements from list to set.

Let’s look into an another better solution,

Check for duplicates in list using Set & looking for first duplicate

Instead of adding all list elements into set and then looking for duplicates. We can add elements one by one to list and while adding check if it is duplicated or not i.e.

Now let’s use this function to check if our list contains any duplicate or not i.e.

Output

Complexity Analysis of this solution

In worst case we will add all elements of list in a set to find that our list doesn’t contain any duplicate. So, worst case complexity will be n(log(n)).
In best case, we will get to know about duplicate as soon as we encounter it during iteration. So, it will be much lesser than n(log(n)).

Let’s look into an another solution.

Check if list contains duplicates using list.count()

Python’s list class provides a method that returns the frequency count of a given element in the list,

It returns the occurrence count of element in the list.

Let’s use this to to check for duplicates,

Here we are iterating over all the elements of list and check count of each element in the list. If count > 1 then it means this element has duplicate entries.

Now let’s use this function to check if our list contains any duplicate or not i.e.

Output

Complexity Analysis of this solution
This is the most inefficient solution till now with complexity O(n^2)

Complete example is as follows,

Output:

Click Here to Subscribe for more Articles / Tutorials like this.