Python – Frequency of elements from other list

Given two lists, compute the frequency of elements of list 2 that occur in list 1.

Input : test_list1 = [4, 6, 8, 9], test_list2 = [4, 6, 6, 5, 8, 10, 4, 9, 8, 10, 1] 
Output : {4: 2, 6: 2, 8: 2, 9: 1} 
Explanation : 4 occurs 2 times, 6 occurs 2 times in second list and so on.

Input : test_list1 = [4, 6, 8, 9], test_list2 = [4, 6, 5, 8, 10, 4, 9, 8, 10, 1] 
Output : {4: 2, 6: 1, 8: 2, 9: 1} 
Explanation : 4 occurs 2 times, 6 occurs 1 time in second list and so on.

Method #1 : Using dictionary comprehension + count()

This is one of the ways in which this task can be performed. In this, count() is used to extract count of elements in list 2, and dictionary comprehension is used to compile results and iterate through list 1 values.

The original list 1 : [4, 6, 8, 9, 10]
The original list 2 : [4, 6, 6, 5, 8, 10, 4, 9, 8, 10, 1]
Lists elements Frequency : {4: 2, 6: 2, 8: 2, 9: 1, 10: 2}

Time complexity: O(n^2) (due to nested loop in count() function)
Auxiliary space: O(n) (dictionary size proportional to size of test_list1)

Method #2 : Using Counter() + setdefault() + loop

This is another way in which this task can be performed. In this, we compute the frequency using Counter() and assign values using loop. The setdefault() is used to initialize the counter to 0 for not present values.

The original list 1 : [4, 6, 8, 9, 10]
The original list 2 : [4, 6, 6, 5, 8, 10, 4, 9, 8, 10, 1]
Lists elements Frequency : {4: 2, 6: 2, 8: 2, 10: 2, 9: 1}

Time complexity:  O(n+m), where n is the length of test_list2.
Auxiliary space: O(n), where n is the length of test_list2.

Method #3: Using operator.countOf()

The original list 1 : [4, 6, 8, 9, 10]
The original list 2 : [4, 6, 6, 5, 8, 10, 4, 9, 8, 10, 1]
Lists elements Frequency : {4: 2, 6: 2, 8: 2, 9: 1, 10: 2}

Time Complexity: O(N)
Auxiliary Space: O(N)

Method #4: Using list comprehension + count() function

Steps:

1. Create an empty dictionary to store the frequency of each element.
2. Loop through each element in the first list.
3. Use the count() function to count the number of occurrences of the element in the second list.
4. Add the element and its frequency to the dictionary.
5. Print the resulting dictionary.

The original list 1 : [4, 6, 8, 9, 10]
The original list 2 : [4, 6, 6, 5, 8, 10, 4, 9, 8, 10, 1]
Lists elements Frequency : {4: 2, 6: 2, 8: 2, 9: 1, 10: 2}

Time complexity: O(n^2) – count() function has a time complexity of O(n), and we are using it n times for n elements in the first list.
Auxiliary space: O(n) – we are using a dictionary to store the frequency of each element.

METHOD 5:Using nested loop and dictionary

APPROACH:

In this problem, we are given two lists and we need to find the frequency of elements in the second list which are present in the first list.

ALGORITHM:

1.Initialize an empty dictionary frequency to store the frequency of elements from list1.
2.Traverse each element of list1 using a for loop.
3.Initialize a counter variable count to 0.
4.Traverse each element of list2 using another for loop and check if the current element of list2 is equal to the current element of list1. If true, increment the counter variable count by 1.
5.Store the frequency count of the current element of list1 in the frequency dictionary.
6.Repeat steps 2-5 for each element of list1.
7.Print the frequency dictionary.

Lists elements Frequency : {4: 2, 6: 2, 8: 2, 9: 1, 10: 2}

Time Complexity:
The time complexity of the above algorithm is O(n^2), where n is the length of the second list.

Space Complexity:
The space complexity of the above algorithm is O(m), where m is the length of the first list. The dictionary frequency will store at most m key-value pairs.