Python: Find Duplicates in a list with Frequency Count and index positions

A collection is an ordered list of values. There could be various types of values. A list is a mutable container. This means that existing ones can be added to, deleted from, or changed.

The Python list represents the mathematical concept of a finite sequence. List values are referred to as list items or list elements. The same value may appear multiple times in a list. Each event is regarded as a distinct element.

Given a list, the task is to find Duplicate elements in a list with their respective frequencies and index positions.

Example:

I)Without indices

Input:

givenlist = [1, 2, 3, 1, 2, 1, 5, 6, 7, 8, 9]

Output:

element = 1 frequency : 3
element = 2 frequency : 2

II)With Indices

Input:

givenlist = [1, 2, 3, 1, 2, 1, 5, 6, 7, 8, 9]

Output:

element = 1 frequency : 3 indices : [0, 3, 5]
element = 2 frequency : 2 indices : [1, 4]

Find Duplicates in a list

There are several ways to find duplicates in a list some of them are:

Method #1:Using set method

  • Remove all duplicates from the list by converting it to a set.
  • Now, traverse the set and use the count() function to determine the frequency of each element.
  • If the frequency is greater than 1 then print the element and frequency

Below is the implementation:

# givenlist
givenlist = [1, 2, 3, 1, 2, 1, 5, 6, 7, 8, 9]
# converting givenlist to set
setlist = set(givenlist)
# Traverse the set
for element in setlist:
    # counting the frequency of element if it is greater than 1 then print it
    frequency = givenlist.count(element)
    if(frequency > 1):
        # print the element and frequency
        print('element =', element, 'frequency :', frequency)

Output:

element = 1 frequency : 3
element = 2 frequency : 2

Time Complexity: O(n^2)

Method #2:Using dictionary

We’ll write a function that takes a list and prints the duplicate elements in that list, as well as their frequency counts.

Approach:

  • This function produces a new dictionary when it is called. The program┬áthen goes through each element in the provided list one by one. It examines each variable to see if it is present in the dictionary keys.
  • If the element does not appear in the dictionary keys, it is added to the dictionary as a key with the value of 1.
    If the element is present in dictionary keys, the value of that key is increased by one.
  • Traverse the dictionary
  • If the frequency is greater than 1 then print the element and frequency

Below is the implementation:

# function which print the duplicates
def printDuplicates(givenlist):
    # taking a empty dictionary
    freq = {}
    # Traverse the list
    for element in givenlist:
        # if the element is in freq dictionary then add its count
        if element in freq.keys():
            freq[element] += 1
        else:
            freq[element] = 1

    # Traverse the freq dictionary and print the duplicate elements and frequency
    for key in freq:
        # if value/count is greater than 1 the print it
        if(freq[key] > 1):
            print('element =', key, 'frequency :', freq[key])


# givenlist
givenlist = [1, 2, 3, 1, 2, 1, 5, 6, 7, 8, 9]
# passing list to printDuplicates function
printDuplicates(givenlist)

Output:

element = 1 frequency : 3
element = 2 frequency : 2

Time Complexity: O(n)

Method #3:Using Counter() function

We can use an iterable or any dict like mapping to construct a Counter class object. This Counter object keeps track of how many times each variable in the iterable has been counted. Let’s use the Counter object to locate and count duplicates in a list.

This function is similar to first two points in method 2

Below is the implementation:

from collections import Counter
# function which print the duplicates


def printDuplicates(givenlist):
    # using Counter function to calculate frequencies
    freq = Counter(givenlist)

    # Traverse the freq dictionary and print the duplicate elements and frequency
    for key in freq:
        # if value/count is greater than 1 the print it
        if(freq[key] > 1):
            print('element =', key, 'frequency :', freq[key])


# givenlist
givenlist = [1, 2, 3, 1, 2, 1, 5, 6, 7, 8, 9]
# passing list to printDuplicates function
printDuplicates(givenlist)

Output:

element = 1 frequency : 3
element = 2 frequency : 2

Time Complexity: O(n)

Method #4:Finding indices and frequency of duplicate elements

Approach:

  • let us take starting index as 0
  • This function produces a new dictionary when it is called. The program┬áthen goes through each element in the provided list one by one. It examines each variable to see if it is present in the dictionary keys.
  • Then iterates through each element in the list one by one, keeping track of the index positions.
  • Then, for each element, it checks to see if it already exists in the dictionary keys.
  • If it doesn’t, it creates a new key-value pair in the dictionary, with the element as the key and a list object of two items as the value. 1)count as 1 2) index list with current index position
  • If the element is found in the dictionary keys, the frequency count in the value field is increased, and the index location in the index list is added.
  • Increment the index by 1 for every iteration
  • Traverse the dictionary
  • If the frequency is greater than 1 then print the element and frequency and indices

Below is the implementation:

def printDuplicates(givenlist):
    # taking a empty dictionary
    freq = {}
    # taking index =0
    index = 0
    # Traverse the list
    for element in givenlist:
        # if the element is in freq dictionary then add its count and index
        if element in freq.keys():
            freq[element][0] += 1
            freq[element][1].append(index)
        else:
            freq[element] = [1, [index]]
        # increment the index
        index += 1

    # Traverse the freq dictionary and print the duplicate elements and frequency
    for key in freq:
        # if value/count is greater than 1 the print it
        if(freq[key][0] > 1):
            print('element =', key, 'frequency :',
                  freq[key][0], 'indices :', freq[key][1])


# givenlist
givenlist = [1, 2, 3, 1, 2, 1, 5, 6, 7, 8, 9]
# passing list to printDuplicates function
printDuplicates(givenlist)

Output:

element = 1 frequency : 3 indices : [0, 3, 5]
element = 2 frequency : 2 indices : [1, 4]

Time Complexity: O(n)

 
Related Programs: