5 Best Ways to Find a Target Value in a Matrix with Python

Rate this post

πŸ’‘ Problem Formulation: It is often necessary to determine the presence of a specific target value within a structured two-dimensional array, or a matrix. Given a matrix represented as a list of lists in Python and a target integer, the task is to verify whether the target value exists within the matrix. For example, if we have a matrix [[1, 2, 3], [4, 5, 6], [7, 8, 9]] and the target value is 5, the program should return True as the output because the value exists in the matrix.

Method 1: Brute Force Search

This method entails a straightforward approach whereby each element in the matrix is compared with the target value sequentially until a match is found or the entire matrix has been searched. The brute force method is simple and requires no pre-sorting or additional data structures. It’s most effective on small to medium-sized matrices.

Here’s an example:

def find_target(matrix, target):
    for row in matrix:
        if target in row:
            return True
    return False

matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
target = 5
print(find_target(matrix, target))

Output: True

This code snippet defines a function find_target() that takes a matrix and a target value as arguments. It iterates through each row and checks if the target is present in the row using Python’s in keyword. It returns True immediately if the target is found, else False after completing the search.

Method 2: Binary Search on Each Row

When each row of the matrix is sorted, a binary search can be used to locate a target value efficiently. This method halves the search space with each iteration, offering a faster search time compared to the brute force method, especially for larger matrices with sorted rows.

Here’s an example:

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return True
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return False

def find_target(matrix, target):
    for row in matrix:
        if binary_search(row, target):
            return True
    return False

matrix = [[1, 3, 5], [2, 6, 9], [4, 7, 10]]
target = 6
print(find_target(matrix, target))

Output: True

The code presents a function find_target() that uses a helper function binary_search() to perform a binary search on each row. The binary search effectively halves the number of elements to check with each iteration, leading to a potentially faster search than the brute force method. This works best when the matrix has sorted rows.

Method 3: Divide and Conquer

This method uses a divide and conquer strategy by comparing the target with the middle element of the matrix and then narrowing down the search area based on this comparison. It’s especially efficient for matrices that are sorted both row-wise and column-wise.

Here’s an example:

def find_target(matrix, target):
    if not matrix:
        return False

    def search_rec(left, up, right, down):
        if left > right or up > down:
            return False
        elif target  matrix[down][right]:
            return False

        mid = left + (right - left) // 2

        row = up
        while row <= down and matrix[row][mid] <= target:
            if matrix[row][mid] == target:
                return True
            row += 1

        return search_rec(left, row, mid - 1, down) or search_rec(mid + 1, up, right, row - 1)

    return search_rec(0, 0, len(matrix[0]) - 1, len(matrix) - 1)

matrix = [[1, 4, 7, 11], [2, 5, 8, 12], [3, 6, 9, 16], [10, 13, 14, 17]]
target = 14
print(find_target(matrix, target))

Output: True

This snippet includes a function find_target() that employs a divide and conquer approach. It defines a recursive function search_rec() which breaks down the search area into smaller parts based on the comparison of the target with the middle element. If the target is within the bounds defined by left, up, right, and down, the function continues to search recursively.

Method 4: Flattening the Matrix

This method involves flattening the matrix into a single list and then using Python’s list search to find the target value. It simplifies the matrix structure at the expense of extra memory usage. This method can be a straightforward solution if you don’t have constraints on space complexity.

Here’s an example:

def find_target(matrix, target):
    flat_matrix = [item for row in matrix for item in row]
    return target in flat_matrix

matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
target = 6
print(find_target(matrix, target))

Output: True

The function find_target() in the example flattens the matrix using list comprehension, creating a single list which is then searched for the target value using in. The approach converts the matrix into a single dimension, making the search process straightforward but potentially inefficient in terms of space.

Bonus One-Liner Method 5: Using any() Function

A concise and elegant approach makes use of Python’s built-in any() function, which checks if any element within an iterable satisfies a particular condition. When combined with a generator expression, it becomes a compact one-liner that’s easy to read.

Here’s an example:

find_target = lambda matrix, target: any(target in row for row in matrix)

matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
target = 5
print(find_target(matrix, target))

Output: True

Here, the function find_target() is defined as a lambda expression that uses any() to check each row for the presence of the target. This one-liner combines readability with efficiency, making it an elegant solution for searching a target in the matrix.

Summary/Discussion

  • Method 1: Brute Force Search. Strengths: Easy to implement. No prerequisites on matrix organization. Weaknesses: Potentially slow for large matrices.
  • Method 2: Binary Search on Each Row. Strengths: Faster than brute force for sorted matrix rows. Weaknesses: Requires sorted rows. Not the most optimal for unsorted matrices.
  • Method 3: Divide and Conquer. Strengths: Efficient for row and column-wise sorted matrices. Weaknesses: Complexity increases for large matrices.
  • Method 4: Flattening the Matrix. Strengths: Simplifies the search into a single list. Weaknesses: Increased space complexity.
  • Method 5: Using any() Function. Strengths: Compact and readable one-liner. Weaknesses: May not offer the same performance benefits as more optimized approaches.