Algorithms for Coding Interviews in Python/

...

/

Solution: Search in a 2D List

Solution: Search in a 2D List

This review lesson gives a detailed analysis of how to search a number in a 2D List.

We'll cover the following...

Solution #1: brute force

Python 3.5
def find_in(lst, number):
    """
    A function to find a number in a 2D list
    :param lst: A 2D list of integers
    :param number: A number to be searched in the 2D list
    :return: True if the number is found, otherwise False
    """
    
    for i in range(len(lst)):  # Number of rows
        for j in range(len(lst[0])):  # Number of cols
            if lst[i][j] == number:  # If number is found
                return True
            
    return False  # If number is not found
# Driver to test above code
if __name__ == '__main__':
    
    lst = [
        [10, 11, 12, 13],
        [14, 15, 16, 17],
        [27, 29, 30, 31],
        [32, 33, 39, 50]
    ]
    # Example 1
    print(find_in(lst, 30))
    # Example 2
    print(find_in(lst, 100))

Explanation

Here, we performed a simple linear search in the entire 2D list using two for loops.

Time complexity

Since we use two nested for loops, the time complexity is O(n∗m)O(n*m) ...