Python | Element Occurrence in dictionary of list values

Sometimes we can have a task in which we are required to count the occurrences of test elements in list or winning numbers, against the numbers with the associated keys with list as values. This can have applications in gaming or other utilities. Let’s discuss certain ways in which this can be done. 

Method #1: Using dictionary comprehension + sum() 

This task can be performed using the combination of above two utilities in which we use dictionary comprehension to bind the logic and sum function can be used to perform the summation of the matches found from test list. 

The original dictionary : {'Akshat': [1, 4, 5, 3], 'Nikhil': [4, 6], 'Akash': [5, 2, 1]}
The original list : [2, 1]
The summation of element occurrence : {'Akshat': 1, 'Nikhil': 0, 'Akash': 2}

Time complexity: O(n), where n is the number of elements in the dictionary values.
Auxiliary space: O(n), as a new dictionary is created to store the result.

Method #2: Using collections.Counter() 

Python offers an inbuilt function that performs the task of extracting the frequency and using this and conditioning to presence in test list, we can solve the above problem using this function. 

The original dictionary : {'Akshat': [1, 4, 5, 3], 'Nikhil': [4, 6], 'Akash': [5, 2, 1]}
The original list : [2, 1]
The summation of element occurrence : {'Akshat': 1, 'Akash': 2}

Time Complexity: O(n^2), where n is the total number of elements in the dictionary values and the test list.
Auxiliary Space: O(m), where m is the number of keys in the dictionary. 

Method #3 : Using count() method

The original dictionary : {'Akshat': [1, 4, 5, 3], 'Nikhil': [4, 6], 'Akash': [5, 2, 1]}
The original list : [2, 1]
The summation of element occurrence : {'Akshat': 1, 'Nikhil': 0, 'Akash': 2}

Method #4: Using nested loops

1. Initialize a dictionary test_dict with some key-value pairs where the value is a list of integers.
2. Initialize a list test_list with some integers.
3. Print the original dictionary and the original list.
4. Using list comprehension and the sum() function, iterate through each value in the dictionary and count the number of occurrences of elements in the given list.Create a new dictionary res with the same keys as the original dictionary and the corresponding values as the counts obtained in the previous step.
5. Print the resulting dictionary res containing the summation of element occurrence.

The original dictionary : {'Akshat': [1, 4, 5, 3], 'Nikhil': [4, 6], 'Akash': [5, 2, 1]}
The original list : [2, 1]
The summation of element occurrence : {'Akshat': 1, 'Nikhil': 0, 'Akash': 2}

Time complexity: O(n*m), where n is the number of key-value pairs in the dictionary and m is the maximum length of any value list.
Auxiliary space: O(n), where n is the number of key-value pairs in the dictionary, for the output dictionary.

Method #5: Using list comprehension + sum() + dictionary comprehension

Approach:

1. Create a dictionary comprehension that iterates over test_dict items with key-value pairs (key, value) using the syntax {key: value for key, value in iterable}.
2. The value in each key-value pair will be a list comprehension that counts the number of times a number in test_list appears in the current value list. The list comprehension uses the syntax [expression for item in iterable if condition], where expression is 1 (i.e., we want to count the number of times an element in test_list appears), item is num (i.e., the current number being checked), and the condition is if num in test_list (i.e., only count the number if it appears in test_list).
3. Finally, wrap the list comprehension in the sum() function to count the number of times the current number appears in value.
4. Return the resulting dictionary comprehension.

The summation of element occurrence : {'Akshat': 1, 'Nikhil': 0, 'Akash': 2}

Time complexity: O(n * m), where n is the number of key-value pairs in test_dict and m is the length of the longest list in test_dict.

Auxiliary space: O(n), where n is the number of key-value pairs in test_dict. The space is used to store the resulting dictionary r

Method  6: Using set intersection

1. Convert the test_list to a set.
2. Iterate through the dictionary using a for loop.
3. For each key-value pair in the dictionary, convert the value list to a set and find the intersection between the two sets using the ‘&’ operator.
4. The length of the resulting set is the count of the elements in the value list that are also in the test_list.
5. Store the count in the final dictionary.
6. Return the final dictionary as the result.

The summation of element occurrence : {'Akshat': 1, 'Nikhil': 0, 'Akash': 2}

Time Complexity: O(n*m), where n is the number of keys in the dictionary and m is the maximum length of the value list.
Auxiliary Space: O(n), where n is the number of keys in the dictionary.