Python supports a list as its list element and hence a matrix can be formed. Sometimes we might have a utility in which we require to perform a search in that list of list i.e matrix and its a very common in all the domains of coding. Let’s discuss certain ways in which this can be performed.
Method #1 : Using any() + list comprehension The any function can be used to perform the task of if condition and the check for each element in the nested list can be computed using the list comprehension.
Python3
# Python3 code to demonstrate# Search in Matrix# using any() + list comprehension# initializing listtest_list = [[4, 5, 6], [10, 2, 13], [1, 11, 18]]# printing original list print("The original list : " + str(test_list))# using any() + list comprehension# to Search in Matrixres = any(13 in sub for sub in test_list)# printing resultprint("Is 13 present in Matrix ? : " + str(res)) |
The original list : [[4, 5, 6], [10, 2, 13], [1, 11, 18]] Is 13 present in Matrix ? : True
Method #2 : Using set.issubset() + itertools.chain() The issubset method can be used to check for the membership in sublist and chain function can be used to perform this task for the each element in the Matrix, in a faster way as it works on iterators.
Python3
# Python3 code to demonstrate# Search in Matrix# using set.issubset() + itertools.chain()from itertools import chain# initializing listtest_list = [[4, 5, 6], [10, 2, 13], [1, 11, 18]]# printing original list print("The original list : " + str(test_list))# using set.issubset() + itertools.chain()# to Search in Matrixres = {13}.issubset(chain.from_iterable(test_list))# printing resultprint("Is 13 present in Matrix ? : " + str(res)) |
The original list : [[4, 5, 6], [10, 2, 13], [1, 11, 18]] Is 13 present in Matrix ? : True
Method #3 : Using Counter() function
Python3
# Python3 code to demonstrate# Search in Matrixfrom collections import Counter# initializing listtest_list = [[4, 5, 6], [10, 2, 13], [1, 11, 18]]# printing original listprint("The original list : " + str(test_list))res = FalsematrixElements = []for i in test_list: matrixElements.extend(i)freq = Counter(matrixElements)if 13 in freq.keys(): res = True# printing resultprint("Is 13 present in Matrix ? : " + str(res)) |
The original list : [[4, 5, 6], [10, 2, 13], [1, 11, 18]] Is 13 present in Matrix ? : True
Time Complexity:O(N*N)
Auxiliary Space: O(N*N)
Method #4:Using reduce()
1. Set the flag variable res to False
2. Initialize an empty list matrixElements
3. For each row in matrix, do the following:
a. Append each element of the row to matrixElements
4. Check if the target element is in matrixElements:
a. If it is, set res to True
5. Return the value of res as the result
Python3
# Python3 code to demonstrate# Search in Matrix using reducefrom functools import reduce# initializing listtest_list = [[4, 5, 6], [10, 2, 13], [1, 11, 18]]# printing original listprint("The original list : " + str(test_list))res = FalsematrixElements = reduce(lambda x, y: x + y, test_list)if 13 in matrixElements: res = True# printing resultprint("Is 13 present in Matrix ? : " + str(res))# THis code is contributed by Vinay Pinjala. |
The original list : [[4, 5, 6], [10, 2, 13], [1, 11, 18]] Is 13 present in Matrix ? : True
The time complexity of the algorithm for searching an element in a matrix using the Counter module or reduce function is O(mn), where m is the number of rows and n is the number of columns in the matrix.
The space complexity of the algorithm is also O(mn), since we are flattening the matrix into a 1D list that contains all the elements of the matrix. This list requires space proportional to the total number of elements in the matrix.
Method #5: Using numpy:
Algorithm:
- Initialize a list of lists (matrix) with the given elements.
- Use the numpy isin function to check if the given element (13 in this case) is present in the matrix.
- Use the any function on the resulting boolean array to check if at least one True value exists.
- Print the result.
Python3
import numpy as np# initializing listtest_list = [[4, 5, 6], [10, 2, 13], [1, 11, 18]]# printing original listprint("The original list : " + str(test_list))# using numpy to search in matrixres = np.isin(test_list, 13).any()# printing resultprint("Is 13 present in Matrix ? : " + str(res))# This code is contributed by Rayudu. |
Output: The original list : [[4, 5, 6], [10, 2, 13], [1, 11, 18]] Is 13 present in Matrix ? : True
Time Complexity:
The time complexity of this code is O(m*n), where m and n are the dimensions of the matrix. The numpy isin function has a linear time complexity.
Auxiliary Space:
The space complexity of this code is O(mn), where m and n are the dimensions of the matrix. This is because the numpy array created to store the matrix elements takes up O(mn) space.
Using numpy.where to search elements in a Matrix:
Algorithm:
Convert the matrix into a numpy array using numpy.array()
Use numpy.where() to get the indices where the target element is present
Convert the indices into a list using tolist() method
Print the result in the desired format
Python3
import numpy as np# initializing matrixtest_list = [[4, 5, 6], [10, 2, 13], [1, 11, 18]]# printing original listprint("The original list : " + str(test_list))# convert the matrix into a numpy arraymatrix = np.array(test_list)# target element to searchtarget = 13# use numpy.where() to get the indices where the target element is presentindices = np.argwhere(matrix == target).tolist()# print the result in the desired formatif len(indices) > 0: print(f"Is {target} present in Matrix ? : True")else: print(f"Is {target} present in Matrix ? : False") |
Output:
The original list : [[4, 5, 6], [10, 2, 13], [1, 11, 18]]
Is 13 present in Matrix ? : True
Time Complexity: O(m*n), where m is the number of rows and n is the number of columns in the matrix. This is because we need to traverse the entire matrix to find the target element.
Auxiliary Space: O(m*n), as we are converting the matrix into a numpy array and creating a list of indices where the target element is present. The space used by numpy is proportional to the number of elements in the matrix.
