Given a list of lists, write a Python program to count the number of sublists containing the given element x. Examples:
Input : lst = [1, 3, 5], [1, 3, 5, 7], [1, 3, 5, 7, 9]]
x = 1
Output : 3
Input : lst = (['a'], ['a', 'c', 'b'], ['d'])
x = 'a'
Output : 2
Approach #1 : Naive Approach Count the number of lists containing x. Initialize count to 0, then start a for loop and check if x exists in each list or not. If yes, increment count.
Python3
# Python3 Program to count number of# list containing a certain element # in a list of listsdef countList(lst, x): count = 0 for i in range(len(lst)): if x in lst[i]: count+= 1 return count # Driver Codelst = (['a'], ['a', 'c', 'b'], ['d']) x = 'a'print(countList(lst, x)) |
2
Time Complexity: O(n)
Auxiliary Space: O(1)
Approach #2 : List comprehension (Alternative for naive) A simple one-liner list comprehension can also do the job by simply converting the above mentioned Naive approach into one-liner for loop.
Python3
# Python3 Program to count number of# list containing a certain element # in a list of listsdef countList(lst, x): return sum(x in item for item in lst) # Driver Codelst = (['a'], ['a', 'c', 'b'], ['d']) x = 'a'print(countList(lst, x)) |
2
Time Complexity: O(n), where n is the number of elements in the list “test_list”.
Auxiliary Space: O(n), where n is the number of elements in the list “test_list”.
Approach #3 : Using chain.from_iterable() and Counter We can use Counter to count how many lists ‘x’ occurs in. Since we don’t want to count ‘x’ for more than once for each inner list, we’ll convert each inner list to sets. After this, join those sets of elements into one sequence using chain.from_iterable().
Python3
# Python3 Program to count number of# list containing a certain element # in a list of listsfrom itertools import chainfrom collections import Counterdef countList(lst, x): return Counter(chain.from_iterable(set(i) for i in lst))[x] # Driver Codelst = (['a'], ['a', 'c', 'b'], ['d']) x = 'a'print(countList(lst, x)) |
2
Time Complexity: O(n), where n is the length of the list
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the list
Approach #4 : Using reduce()
Here is an approach using the reduce function from the functools module:
Python3
from functools import reducedef count_sublists_containing_element(lst, x): # Use reduce to iterate over each sublist in lst and keep a running total # of how many sublists contain x. If x is in the sublist, add 1 to the total. # Otherwise, add 0. return reduce(lambda total, sublist: total + (1 if x in sublist else 0), lst, 0)lst = [[1, 3, 5], [1, 3, 5, 7], [1, 3, 5, 7, 9]]x = 1print(count_sublists_containing_element(lst, x)) # prints 3lst = (['a'], ['a', 'c', 'b'], ['d'])x = 'a'print(count_sublists_containing_element(lst, x)) # prints 2#This code is contributed by Edula Vinay Kumar Reddy |
3 2
This approach uses the reduce function to iterate over each sublist in lst and keep a running total of how many sublists contain x. It uses a lambda function as the first argument to reduce, which takes in a total variable representing the running total and a sublist variable representing the current sublist being processed. If x is in the current sublist, it adds 1 to the total. Otherwise, it adds 0. The third argument to reduce is the initial value of the total variable, which is set to 0.
Time complexity: O(n), where n is the number of sublists in lst. The reduce function iterates over each sublist in lst once to check if x is in it.
Auxiliary Space: O(1). The reduce function only stores the running total in memory, which takes up a constant amount of space.
